E. Оньс 1D

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Валерад хоёр чиглэлд хязгааргүй нүднүүдээс тогтсон тууз байна. Нүднүүд бүхэл тоонуудаар дугаарлагдсан. $0$ дугаартай нүдэнд робот байна.

Роботод түүний гүйцэтгэх ёстой үйлдлүүдийн дараалал болох зааврууд байна. Нэг үйлдэлд робот зааврын дагуу нэг зүүн талын эсвэл нэг баруун талын нүдрүү хөдлөнө. Робот хөдлөж эхлэхээс өмнө Валера $0$-с бусад зарим нүднүүдэд саад байрлуулна. Хэрвээ робот зааврын дагуу саадтай нүдрүү хөдлөх ёстой байвал энэ үйлдлээ алгасна.

Мөн Валера робот бүх заавруудыг гүйцэтгэсний дараа дуусах нүдийг тодорхойлно. Дуусах нүд эхлэх нүднээс ялгаатай байх ёстой. Хэрвээ робот хөдөлгөөнөө дуусахдаа л дуусах нүдэнд ганц удаа очсон бол заавруудыг амжилттай гүйцэтгэсэн гэж тооцно. Түүнчлэн сүүлийн үйлдлийг алгасахгүй.

Робот заавруудын дарааллаа бүрэн гүйцэтгэх ба нэг нүдэнд дуусах боломжтой болгохын тулд Валеригийн тавих саадуудын хамгийн бага тоог $k$ гэе. Та Валери $k$ саад болон дуусах нүд сонгох хэдэн ялгаатай зам байхыг тооцоолох ёстой ба робот заавруудаа амжилттай гүйцэтгэх ёстой.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдаагүй тэмдэгтүүдийн дараалал $s_{1}s_{2}... s_{n}$ $(1 ≤ n ≤ 10^{6})$ байх ба зөвхөн "$L$" ба "$R$" үсгүүдээс бүрдэнэ. Хэрвээ $s_{i}$ нь "$L$" байвал робот $i$-р үйлдэлдээ зүүн тийшээ нэг нүд явахыг оролдох ёстой. Хэрвээ $s_{i}$ нь "$R$" байвал робот $i$-р үйлдэлдээ баруун тийшээ нэг нүд явахыг оролдох ёстой.

Гаралт

Ялгаатай замуудын тоо болох нэг бүхэл тоон утгыг хэвлэ. Энэ тоо нь 64-битийн бүхэл тоон төрөлтэй таарч байх ёстой.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
RR
Гаралт
1
Оролт
RRL
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр Валера ямар ч саад тавих ёсгүй ба түүний дуусах нүд нь $2$ байх ёстой.

Хоёр дахь жишээн дээр Валера $1$ дугаартай нүдэнд саад байрлуулах ёстой ба түүний дуусах нүд $ - 1$ байх ёстой. Энэ тохиолдолд робот эхний хоёр үйлдлийг алгасах ба гурав дахь үйлдэлд тэр эхлэх нүднээс шууд дуусах нүдрүү хөдлөх ёстой. Гэхдээ хэрвээ Валера ямар ч саад тавихгүй эсвэл өөр нүдэнд байрлуулвал робот дуусах нүдэнд нэгээс олон удаа очино.

Сэтгэгдлүүдийг ачааллаж байна...