Бурмотіння в стаді (Золото)
Це маловідомий факт, що у корів є свій алфавіт - "cowphabet". Він складається з 26 літер від 'a' до 'z', але порядок літер у цьому "cowphabet" може відрізнятися від стандартного порядку 'abcdefghijklmnopqrstuvwxyz'.
Щоб розважитися, Мілдред постійно бурмоче cowphabet. Фермер Нхой хоче дізнатися, скільки разів вона пробурмотіла cowphabet.
Вам дано рядок літер, які почув ФН. Обчисліть мінімальну кількість разів, яку Мілдред пробурмотіла весь cowphabet. ФН міг не почути деякі з літер, які бурмотіла Мілдред.
Зауваження: час на тестування цього завдання подвоєно.
Вхідні дані
Єдиний рядок вводу містить рядок малих літер, які почув ФН. Цей рядок має довжину від 1 до 10^5.
Вихідні дані
Виведіть мінімальну кількість разів, яку Мілдред вимовила весь cowphabet.
Приклад
Мілдред вимовила cowphabet не менше трьох разів. Це можливо, якщо cowphabet починається з mildre і ФН чув літери, які позначені великими літерами, як показано нижче.
MILDREabcfghjknopqstuvwxyz milDREabcfghjknopqstuvwxyz mildrEabcfghjknopqstuvwxyz