C. Хүнд бодлого

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

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

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

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

Васили өөр өөр бодлогууд бодох дуртай нэгэн юм. Өнөөдөр тэрээр нэгэн өөрийн бодож чадахгүй бодлогыг олсон ба иймд тэрээр таны тусламжийг хүсжээ.

Васили-д Англи жижиг үсгүүдээс тогтох $n$ ширхэг тэмдэгт мөр өгөгджээ. Тэрээр эдгээр тэмдэгт мөрүүдийг хэл зүйн дарааллаар (толь бичигт ашигладаг дарааллыг хэл зүйн дараалал гэнэ) нь эрэмбэлэхийг хүсэж байгаа боловч тэрээр эдгээр тэмдэгт мөрүүдийг хооронд сольж болохгүй байв. Түүний хийж чадах цорын ганц үйлдэл нь тэрээр эдгээр тэмдэгт мөрүүдийн алийг нь ч урвуулж чадна (өөрөөр хэлбэл эхний тэмдэгт нь сүүлийн тэмдэгт болно, 2-дахь тэмдэгт нь сүүлээсээ 2-дахь тэмдэгт болно гэх мэтчилэн үргэлжлэх юм).

$i$-дахь тэмдэгт мөрийг урвуулахын тулд Васили $c_{i}$ нэгж энерги зарцуулах ажээ. Тэрээр уг тэмдэгт мөрүүдийг хэл зүйн дарааллаар нь эрэмбэлэхийн тулд хамгийн бага хэмжээний энерги зарцуулах сонирхолтой байв.

Хэрэв тэмдэгт мөр $A$ нь $B$-ээс богино ($|A| < |B|$) бөгөөд $B$ тэмдэгт мөрийн угтвар бол, эсвэл хэрэв эдгээрийн аль нь ч нөгөө нэгнийхээ угтвар биш бөгөөд эдгээр тэмдэгт мөрүүд дэх эхний ялгаатай тэмдэгтүүдийн хувьд $A$-дахь тэмдэгт нь $B$-дэх тэмдэгтээсээ бага байвал тэмдэгт мөр $A$-г тэмдэгт мөр $B$-ээс хэл зүйн хувьд бага байна гэж үзнэ.

Уг бодлогод тохируулан зэрэгцээ байрлаж буй 2 тэнцүү тэмдэгт мөрүүдийг хэл зүйн дарааллын нөхцөлийг зөрчихгүй байна гэж үзэх юм.

Оролт

Оролтын эхний мөрөнд тэмдэгт мөрүүдийн тоог илэрхийлэх бүхэл тоо $n$ ($2 ≤ n ≤ 100 000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $c_{i}$ ($0 ≤ c_{i} ≤ 10^{9}$)-ууд өгөгдөх ба эдгээрийн $i$-дахь нь Васили-ын $i$-дахь тэмдэгт мөрийг урвуулахын тулд зарцуулах энергийн хэмжээтэй тэнцүү байх юм.

Дараа нь $n$ ширхэг мөр өгөгдөх ба, мөр болгонд Англи жижиг үсгүүдээс тогтох нэг ширхэг тэмдэгт мөр өгөгдөнө. Эдгээр тэмдэгт мөрүүдийн нийт урт нь $100 000$-аас хэтрэхгүй байна.

Гаралт

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

Орчуулсан: Баатархүү

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

Оролт
2
1 2
ba
ac
Гаралт
1
Оролт
3
1 3 1
aa
ba
ac
Гаралт
1
Оролт
2
5 5
bbb
aaa
Гаралт
-1
Оролт
2
3 3
aaa
aa
Гаралт
-1

Тэмдэглэл

2-дахь жишээнд та $2$-р эсвэл $3$-р тэмдэгт мөрийг урвуулах ёстой юм. Гэхдээ $3$-р тэмдэгт мөрийг урвуулахад шаардагдах энергийн хэмжээ нь илүү бага байна.

3-дахь жишээнд 2 тэмдэгт мөр нь 2-уулаа урвуулсны дараа ч гэсэн өөрчлөгдөхгүй ба тэд буруу эрэмбэтэй байгаа юм. Иймд хариулт нь $ - 1$ байна.

4-дэх жишээнд 2 тэмдэгт мөр нь 2-уулаа зөвхөн 'a' гэсэн тэмдэгтээс тогтох боловч хэл зүйн дарааллын хувьд "aa" гэсэн тэмдэгт мөр нь "aaa" гэсэн тэмдэгт мөрийн өмнө нь байрлах ёстой юм. Иймд хариулт нь $ - 1$ байна.

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