Bir təmirlə fənərlər#13115
Dairə üzərində -dən -ə qədər nömrələnmiş ev yerləşir. Hər evin yanında bir fənər var.
Hər fənər iki qonşu evdən yalnız birini işıqlandırır:
L — soldakı evi;
R — sağdakı evi.
Fənər yanında yerləşdiyi evi işıqlandırmır. -ci evin sol qonşusu i-1-ci ev, sağ qonşusu isə i+1-ci evdir. -ci evin sol qonşusu -ci ev, -ci evin sağ qonşusu isə -ci evdir.
Ən çox bir fənərin istiqamətini L-dən R-ə və ya əksinə dəyişə bilərsiniz.
Bundan sonra dəqiq bir fənərlə işıqlandırılan evlərin mümkün olan maksimal sayını tapın.
Birinci sətirdə bir tam ədədi (3\le n\le2\cdot10^5) — evlərin sayı verilir.
İkinci sətirdə L və R simvollarından ibarət, uzunluğu olan sətri verilir. s_i simvolu -ci evin yanındakı fənərin istiqamətini göstərir.
Bir tam ədəd — dəqiq bir fənərlə işıqlandırılan evlərin mümkün olan maksimal sayını çap edin.
Nümunə 1
Nümunə 2
Nümunə 3
Birinci nümunədə ikinci fənərin istiqamətini dəyişərək RRRRR alırıq. Bundan sonra hər ev dəqiq bir fənərlə işıqlandırılır, buna görə cavab -dir.
İkinci nümunədə başlanğıcda və evlərinin hər biri iki fənərlə işıqlandırılır, və evləri isə işıqlandırılmır. Birinci fənərin istiqamətini dəyişdikdə və evlərinin hər biri dəqiq bir fənərlə işıqlandırılır. İkidən çox belə ev almaq mümkün deyil.
Üçüncü nümunədə dörd evin hamısı artıq dəqiq bir fənərlə işıqlandırılır. Buna görə heç nəyi dəyişməmək olar.
Altməsələ ( bal): n\le100.
Altməsələ ( bal): n\le2000.
Altməsələ ( bal): əlavə məhdudiyyət yoxdur.