Chumolilar
O'yin maydoni $1 \times n$ o'lchamli katakchalardan iborat chiziqdir. Ba'zi kataklarda chumolilar, ba'zilarida esa shakarqandlar (yulduzchalar) bor, qolgan kataklar esa bo'sh.
Chumoli bitta qo'shni katakka o'tishi uchun $1$ birlik vaqt sarflaydi. Agar chumoli shakarqand turgan katakka kirsa, uni darhol iste'mol qiladi.
Barcha chumolilar bir vaqtda harakatlanishni boshlaydi. Har bir chumoli harakat yo'nalishini istalgancha o'zgartirishi mumkin, lekin o'yin maydonidan tashqariga chiqib ketmasligi kerak. Chumolilar bir-biriga xalaqit bermaydi: bir katakda istalgancha chumoli bo'lishi va ular turli yo'nalishlarda harakatlanishi mumkin.
Sizning vazifangiz — barcha shakarqandlarni yeb bitirish uchun kerak bo'ladigan minimal vaqtni topishdir.
Kiruvchi ma'lumotlar
Birinchi satrda o'yin maydonining uzunligini bildiruvchi butun $n$ ($2 \le n \le 10^5$) soni beriladi.
Ikkinchi satrda esa $n$ ta belgidan iborat bo'lgan o'yin maydoni tavsifi keltiriladi. Agar $i$-pozitsiyada '.' (nuqta) belgisi bo'lsa, bu katak bo'shligini, '*' (yulduzcha) belgisi bo'lsa, unda shakarqand borligini, 'P' belgisi bo'lsa, u yerda chumoli borligini anglatadi. O'yin maydonida kamida bitta chumoli va kamida bitta shakarqand borligi kafolatlanadi.
Chiquvchi ma'lumotlar
Misollar
| # | Input TXT | Output TXT |
|---|---|---|
| 1 |
7 *..P*P* |
3 |
| 2 |
10 .**PP.*P.* |
2 |
Izoh
Birinchi misolda 4-pozitsiyadagi chumoli chapga harakatlanib, 1-pozitsiyadagi shakarqandni 3 birlik vaqtda yeydi. Shu vaqt ichida 6-pozitsiyadagi chumoli o'ziga qo'shni bo'lgan 5 va 7-pozitsiyalardagi shakarqandlarni yeyishga ulguradi. Natijada 3 birlik vaqtda barcha shakarqandlar yeb bitiriladi.
Ikkinchi misolda 4-pozitsiyadagi chumoli chapga yurib, 2 birlik vaqtda 3 va 2-pozitsiyalardagi shakarqandlarni yeydi. 5 va 8-pozitsiyalardagi chumolilar esa o'ngga harakatlanib, mos ravishda 7 va 10-pozitsiyalardagi shakarqandlarni iste'mol qiladi. Shunday qilib, barcha shakarqandlarni yeyish uchun jami 2 birlik vaqt kifoya qiladi.