Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X) – se introduce în stivă litera X (evident, în vârful stivei);
pop – se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top – se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push, pop, top, fără a executa pop sau top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
De exemplu, șirul ABCACBA poate fi generat astfel: push(A), top, pop, push(B), top, pop, push(C), top, pop etc.
O altă secvență de operații corectă, dar mai scurtă ar fi: push(A), top, push(B), top, push(C), top, push(A), top, pop, top, pop, top, pop, top, pop.

Cerința

Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.

Date de intrare

Fișierul de intrare stiva2.in conține pe prima linie un șir format numai din litere mari.

Date de ieșire

Fișierul de ieșire stiva2.out va conține o singură linie pe care va fi scris numărul minim de operații dintr-o secvență corecte care afișează șirul din fișierul de intrare.

Restricții și precizări

• Lungimea șirului este de cel mult 500

Exemplu:

stiva2.in

ABCACBA

stiva2.out

15