Вам задана строка \(s\), состоящая из строчных букв латинского алфавита. Пусть длина \(s\) равна \(|s|\).
За один ход вы можете выбрать любой индекс \(i\) и удалить \(i\)-й символ \(s\) (\(s_i\)), если хотя бы один из его соседних символов является предыдущей буквой в латинском алфавите для \(s_i\). Например, для буквы b предыдущей буквой является a, для буквы s предыдущей букой является r, для буквы a предыдущей буквы не существует. Заметьте, что после каждого удаления длина строки уменьшается на единицу. Таким образом, индекс \(i\) должен удовлетворять условию \(1 \le i \le |s|\) в течение каждого хода.
Соседними символами для символа \(s_i\) являются символы \(s_{i-1}\) и \(s_{i+1}\). Первый и последний символы \(s\) имеют только один соседний символ (за исключением случая \(|s| = 1\)).
Рассмотрим следующий пример. Пусть \(s=\) bacabcab.
- В течение первого хода вы можете удалить первый символ \(s_1=\) b, так как \(s_2=\) a. Тогда строка станет равна \(s=\) acabcab.
- В течение второго хода вы можете удалить пятый символ \(s_5=\) c, так как \(s_4=\) b. Тогда строка станет равна \(s=\) acabab.
- В течение третьего хода вы можете удалить шестой символ \(s_6=\) b, так как \(s_5=\) a. Тогда строка станет равна \(s=\) acaba.
- В течение четвертого хода единственным символом, который вы можете удалить, является \(s_4=\) b, так как \(s_3=\) a (или \(s_5=\) a). Строка станет равна \(s=\) acaa, и вы больше не сможете ничего с ней сделать.
Ваша задача — найти максимальное количество символов, которые вы можете удалить, если вы выберете последовательность ходов оптимально.
Выходные данные
Выведите одно целое число — максимально возможное количество символов, которые вы можете удалить, если вы выберете последовательность ходов оптимально.
Примечание
Первый тестовый пример разобран в условии задачи. Заметьте, что последовательность ходов, представленная в условии, не является единственной, но можно показать, что максимально возможный ответ на этот тест равен \(4\).
Во втором тестовом примере вы можете удалить все символы \(s\), кроме одного. Единственный возможный ответ описан ниже.
- В течение первого хода следует удалить третий символ \(s_3=\) d, \(s\) станет равна bca.
- В течение второго хода следует удалить второй символ \(s_2=\) c, \(s\) станет равна ba.
- Наконец, в течение третьего хода следует удалить первый символ \(s_1=\) b, \(s\) станет равна a.