- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
حنا قهرمان مسابقات هندونهخوری شده و مقدار زیادی پول جایزه گرفته است. حال حنا میخواهد به خانهاش برگردد و با پول مسابقات مهمانی بگیرد.
شهر محل زندگی حنا، یک خیابان با \(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
در مسیر خانه هشتم به سوم تنها در خانههای ۴ و ۵ و ۷ زورگیر وجود دارد که پلیسها طی یک مرحله زورگیر خانهی ۴ و ۵ و در مرحلهی بعد زورگیر خانهی ۷ را دستگیر میکنند. در حرکت اول یک بازه به طول ۲ و در حرکت دوم یک بازه به طول ۱ پاکسازی شد که طول هر دو بازه توانی از ۲ بود.