+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حنا قهرمان مسابقات *هندونه‌خوری* شده و مقدار زیادی پول جایزه گرفته‌ است. حال حنا می‌خواهد به خانه‌اش برگردد و با پول مسابقات مهمانی بگیرد. شهر محل زندگی حنا، یک خیابان با $n$ خانه است که حنا در خانه‌ی $s$ام زندگی می‌کند و مسابقات *هندونه‌خوری* در خانه $t$ ام برگزار می‌شود. او می‌داند در تعدادی از خانه‌ها زورگیر زندگی می‌کند و اگر از آن‌ها رد شود، زورگیر پول حنا را از او می‌گیرند و حنا نمی‌تواند مهمانی بگیرد. حنا از پلیس کمک می‌خواهد. پلیس‌ها در روز برنامه‌نویس می‌توانند در هر عملیات، یک بازه به طول $2^k$ ($k$ یک عدد حسابی است) را که **همه اعضای** آن زورگیر هستند را انتخاب کنند و آن خانه‌ها را پاکسازی کنند. پلیس‌ها وقت زیادی ندارند. برای همین از شما می‌خواهند کمترین تعداد عملیات برای پاکسازی مسیر بین حنا و مسابقه *هندونه‌خوری* را بگویید. # ورودی در سطر اول عدد $n$ آمده که نشان‌دهنده‌ی طول خیابان است. در سطر دوم یک رشته به طول $n$ آمده‌است. خانه‌هایی که در آن زورگیر وجود دارد حرف `H` و بقیه خانه‌ها حرف `P` هستند. تضمین می‌شود که در خانه‌های $s$ و $t$ زورگیر وجود ندارد. در سطر سوم $s$ و $t$ به ترتیب آمده‌اند. $$ 1 \leq n \leq 1\ 000 $$ $$ 1 \leq s, t \leq n $$ # خروجی در تنها سطر خروجی، کمترین تعداد عملیات برای پاکسازی مسیر حنا از زورگیرها را بگویید. # مثال # ورودی نمونه ۱ ``` 3 PHP 1 3 ``` # خروجی نمونه ۱ ``` 1 ``` در مسیر خانه اول به سوم، تنها در خانه‌ دوم زورگیر وجود دارد که پلیس‌ها طی یک مرحله او را دستگیر می‌کنند. # ورودی نمونه ۲ ``` 9 HPPHHPHPH 8 3 ``` # خروجی نمونه ۲ ``` 2 ``` در مسیر خانه هشتم به سوم تنها در خانه‌های ۴ و ۵ و ۷ زورگیر وجود دارد که پلیس‌ها طی یک مرحله زورگیر خانه‌ی ۴ و ۵ و در مرحله‌ی بعد زورگیر خانه‌ی ۷ را دستگیر می‌کنند. در حرکت اول یک بازه به طول ۲ و در حرکت دوم یک بازه به طول ۱ پاکسازی شد که طول هر دو بازه توانی از ۲ بود. <details class="blue"> <summary> راهنمایی ۱ </summary> باید زیربازه‌ی خانه $s$ام تا خانه $t$ام را در نظر بگیریم، چرا که بقیه‌ی خانه‌ها تاثیری در مسیر حنا به مسابقه ندارند. حال در این مسیر نیز می‌توانیم بلوک‌های متشکل از خانه‌های سالم را در نظر نگرفته و فقط بلوک‌های خانه‌های حاوی زورگیر را نگاه کنیم (منظور از بلوک تعدادی خانه‌ی متوالی است که ویژگی ما را ندارند و خانه‌های دو سر بلوک ویژگی ما را ندارند). </details> <details class="blue"> <summary> راهنمایی ۲ </summary> حال که خانه‌ها را بلوک‌بندی کردیم و فقط بلوک‌های دارای زورگیر را در نظر می‌گیریم،‌ مسئله را به صورت مجزا برای بلوک‌ها حل می‌کنیم. حال بلوک زورگیر خاصی را در نظر می‌گیریم. بدون لطمه خوردن به کلیت مسئله فرض می‌کنیم که اندازه‌ی بلوک مورد نظر برابر $m$ باشد. با کمی بررسی (در مبنای ۲) متوجه می‌شویم که بهینه‌ترین کار ممکن این است که هر دفعه پلیس‌ها بلندترین پیشوندی که می‌توانند را از بلوک فعلی پاکسازی نمایند. به عبارت دیگر، در هر مرحله $2^{k}$ خانه اول را از زورگیر پاکسازی می‌کند به طوری که $$2^{k} \le m \le 2^{k+1}$$ و سپس مقدار $m$ را برابر اندازه‌ی بلوک جدید قرار می‌دهد (مقدار آن را منهای دو به توان $k$ می‌کند). در واقع اگر در مبنای ۲ به $m$ نگاه کنیم، **حداقل تعداد گامی که لازم است تا این بازه را پاکسازی کنیم، برابر تعداد بیت‌های یک $m$ در مبنای ۲ می‌باشد.** </details>