Brevbäraren

Brevbäraren Harry Kuvert är slarvig. När han idag står i början av den gata, utefter vilken han ska dela ut posten, har han inte sorterat breven.

När han läser på brevet överst i bunten har han två val:

• Antingen stoppar han ned brevet i väskan för att eventuellt dela ut det i morgon

• Eller så söker han upp rätt adress och delar ut brevet

Eftersom Harry bor i slutet av gatan vägrar han att vända och gå tillbaka. De brev som hamnar högst i bunten och vars adress han redan passerat hamnar därför direkt i väskan. Trots allt har Harry ett litet brevbärarhjärta som klappar lite extra när han lyckats, att med sin metod, dela ut så många brev som möjligt.

Skriv ett program som tar emot en sträng med versala bokstäver (A . . . Z), där ingen bokstav kan förekomma fler än en gång. Antalet bokstäver kan variera men dock inte överskrida 26 (glöm inte W). Denna sträng beskriver Harrys brevbunt, med översta brevet först. Eftersom gatan är ’numrerad’ från A till Z ska programmet ta fram den längsta delsekvens ur strängen där bokstäverna är i stigande ordning. Denna delsekvens ger det största möjliga antalet utdelade brev. Något som Harry kan uppnå om han hela tiden gör rätt val.

Input

En sträng med som högst 26 versaler där ingen finns fler än en gång.

Output

Den längsta strängen som utgör en delsekvens av indatasträngen sådan att alla bok- stäver är i bokstavsordning. Om det finns flera likvärdiga lösningar, så räcker det att ange en av dem.

KBWZSROCFUJDEILANTMYGVXHPQ

BCDEILNTVX