Задача F. Алфавитное сжатие ≡

Условие

Недавно компания TIoN разработала новый способ сжатия сообщений.

Сжатие проходит в несколько этапов. Один этап заключается в следующем: в исходном сообщении выбирается такой отрезок из букв, что разница между каждой парой соседних букв на нём равна одному и тому же значению. Разница между двумя буквами равна разнице их позиций в алфавите.

После выбора отрезка он заменяется на "*n.d", где '*' — первая буква отрезка, 'n' — количество букв в отрезке, 'd' — разница между каждой парой соседних букв. Например, отрезок "cdefghi" после сжатия будет выглядеть как "c7.1", а отрезок "geca" — "g4.-2".

После этого начинается новый этап и выбор другого отрезка для сжатия. Разумеется, цель сжатия — уменьшить длину сообщения, поэтому если результат сжатия длиннее, чем исходных отрезок, то такое сжатие не выполняется. Сжатию также не подвергаются символы, получившиеся в результате сжатия других отрезков.

Компании TIoN в срочном порядке необходимо доказать целесообразность существования нового вида сжатия. Для этого им нужно вычислить минимально возможную длину сообщения S после сжатия.

Формат входного файла

Первая строка содержит одно целое число N — длина сообщения.

Вторая строка содержит строку S — сообщение, которое подвергается сжатию.

Строка S состоит из строчных букв латинского алфавита.

Формат выходного файла

Выведите одно целое число — минимальную длину сообщения после сжатия.

Ограничения

1 ≤ N ≤ 10⁵

Пояснение к примерам

В первом примере есть два варианта сжатия сообщения: "x10.0t5.-4" и "x9.0x6.-4". Второй вариант короче первого на 1 символ.

Примеры тестов

15
xxxxxxxxxxtplhd

9

7
cdefghi

4

4
geca

4