A. Витали ба бялуу

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

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

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

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

Хүнд өдрийн дараа Витали маш их өлссөн тул өөрийн дуртай төмсний бялууг идэхийг хүсчээ. Гэхдээ энэ нь тийм ч амархан биш. Витали өрөөнүүд нь зүүнээс баруун тийш нэгээс эхлэн дугаарласан $n$ ширхэг цоожтой өрөөтэй байшингийн эхний өрөөнд байна. Та $1$-р өрөөнөөс $2$-р өрөө рүү, $2$-р өрөөнөөс $3$-р өрөө рүү, $3$-р өрөөнөөс $4$-р өрөө рүү гэх мэтчилэн явсаар $(n-1)$-р өрөөнөөс $n$-р өрөө рүү орох боломжтой. Өөрөөр хэлбэл та $x$-р өрөө рүү зөвхөн $(x-1)$-р өрөөнөөс л орох боломжтой байх нь.

Төмсний бялуу $n$-р өрөөнд байгаа бөгөөд Витали тэр өрөөнд орох ёстой.

Дараалсан хос өрөө бүрийн хооронд хаалга байдаг. $(x-1)$-р өрөөнөөс $x$-р өрөө рүү орохын тулд та тэдгээр өрөөний хооронд байгаа хаалгыг онгойлгох хэрэгтэй.

Байшинд нийт хэд хэдэн төрлийн хаалга (Латин том үсгээр илэрхийлэгдэнэ) болон хэд хэдэн төрлийн түлхүүр (Латин жижиг үсгээр илэрхийлэгдэнэ) байгаа. $t$ болон $T$ ижил үсэг ч гэсэн том жижгээрээ ялгаатай бичигдсэн тохиолдолд $T$ төрлийн хаалгыг $t$ төрлийн түлхүүр онгойлгож чадна. Жишээлбэл $f$ төрлийн түлхүүр $F$ төрлийн хаалгыг онгойлгож чадна.

Эхний $(n-1)$ өрөө бүр Витали дараагийн өрөөнд орохын тулд ашиглаж болох ямар нэг төрлийн нэг ширхэг түлхүүрийг агуулдаг. Ямар нэг түлхүүрээр хаалгыг нээсний дараа Витали цоожны нүхнээс түлхүүрийг авч чадахгүй, тэр даруй дараагийн өрөөнд орно. Өөрөөр хэлбэл түлхүүр бүр нэгээс олон хаалга нээж чадахгүй.

Витали дараагийн өрөөний хаалгыг нээх түлхүүр зарим өрөөнд дуусаж болно гэдгийг ойлгосон байна. Витали төмсний бялуу руу явахаасаа өмнө $n$-р өрөөнд найдвартай хүрэхийн тулд ямар ч төрлийн түлхүүрнээс хэдийг ч авч чадна.

Байшингийн зураг өгөгдсөн байгаа. Тэр амттай төмсний бялуу байгаа $n$-р өрөөнд хүрэхийн тулд худалдан авах хэрэгтэй түлхүүрний хамгийн бага тоог мэдэхийг хүсэж байна. Энэ тоог олоход нь туслах програм бичнэ үү.

Оролт

Оролтын эхний мөрөнд байшингийн өрөөнүүдийн тоо болох $n$ ($2 ≤ n ≤ 10^{5}$) бүхэл тоо байна.

Оролтын хоёр дахь мөрөнд $2 \cdot n - 2$ урттай $s$ тэмдэгт мөр байна. Тэмдэгт мөрийн элементүүдийг зүүнээс нь баруун тийш нэгээс эхлэн дугаарлана.

Өгөгдсөн тэмдэгт мөрийн сондгой байрлалд Латин жижиг үсэгнүүд байна. Энэ нь харгалзах өрөөнд байгаа түлхүүрний төрөл юм. Тиймээс өгөгдсөн $s$ тэмдэгт мөрийн сондгой байрлал болох $i$-р байрлалд байгаа Латин жижиг үсэг нь $(i + 1) / 2$-р өрөөнд байгаа түлхүүрний төрөл юм.

Өгөгдсөн тэмдэгт мөрийн тэгш байрлалд Латин том үсэгнүүд байна. Энэ нь өрөөнүүдийн хоорондох хаалганы төрөл юм. Тэгэхээр өгөгдсөн $s$ тэмдэгт мөрийн тэгш байрлал болох $i$-р байрлалд байгаа Латин том үсэг нь $i / 2$-р өрөөнөөс $(i + 1) / 2 + 1$-р өрөөрүү орох хаалганы төрөл юм.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ бол Витали $n$-р өрөөнд найдвартай хүрэхийн тулд худалдан авах хэрэгтэй түлхүүрнүүдийн хамгийн бага тоо юм.

Орчуулсан: Даариймаа

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

Оролт
3
aAbB
Гаралт
0
Оролт
4
aBaCaB
Гаралт
3
Оролт
5
xYyXzZaZ
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...