Бурмотіння у стаді (Золото)#11201
Маловідомий факт про корів полягає в тому, що вони мають власну версію алфавіту, який називається коров'ячим алфавітом. Він складається з літер від до , але коли корова вимовляє коров'ячий алфавіт, вона перелічує літери у певному порядку, який може відрізнятися від звичайного порядку abcdefghijklmnopqrstuvwxyz.
Щоб згаяти час, кузина Бессі, Мілдред, знову і знову наспівує коров'ячий алфавіт, і фермер Нхой хоче дізнатися, скільки разів вона вже його наспівала.
Дано рядок із малих літер, які фермер Нхой почув від Мілдред. Визначте мінімальну кількість разів, яку Мілдред мала повністю наспівати коров'ячий алфавіт, щоб фермер Нхой міг почути даний рядок. Фермер Нхой не завжди уважно слухає, тому деякі літери з тих, які наспівувала Мілдред, він міг пропустити. Даний рядок містить лише ті літери, які він запам'ятав.
Рядок складається з малих літер, які фермер Нхой почув від Мілдред. Довжина рядка знаходиться в діапазоні від до 10^5 включно.
Виведіть мінімальну кількість разів, яку Мілдред мала повністю наспівати коров'ячий алфавіт.
Мілдред мала наспівати коров'ячий алфавіт щонайменше три рази. Можна зробити так, щоб вона наспівала його рівно три рази, якщо коров'ячий алфавіт починається з "mildre". Літери, які почув фермер Нхой, показані нижче великими літерами:
MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyzПриклад 1