h2. Date de intrare

Fişierul de intrare $palalila2.in$ va contine o singura linie pe care se va afla sirul $S$.

Fişierul de intrare $palalila2.in$ ...

h2. Date de ieşire

În fişierul de ieşire $palalila2.out$ se va afisa pe prima linie lungimea determinata pentru cel mai lung subsir zig-zag al lui $S$.

În fişierul de ieşire $palalila2.out$ ...

h2. Restricţii

* $1 ≤ lungimea sirului S ≤ 500 000$
* Pentru 50% din teste $1 ≤ lungimea sirului S ≤ 4 000$

* $... ≤ ... ≤ ...$

h2. Exemplu