Рядки в Ужляндiї#171

Рядки в Ужляндiї

В Ужляндії знову щось трапилось! Сьогодні відзначає свій день посвяти у лицарі Головний Ужляндський Дитар – Маша. За традицією їй задали Головний Ужляндський Рядок довжини , що складається з маленьких букв англійського алфавіту. Символи рядка пронумеровані від 1 до .

Щоб пройти порічне випробування, Маші необхідно дістатися останнього елементу рядка, отриманими максимальну кількість балів. Правила випробування та нарахування балів такі:

На жаль, журі випробування не знає яку ж насправді максимальну кількість балів можна отримати. Саме тому воно доручило Вам знайти це значення.

Input

У першому рядку вхідного файлу знаходиться одне ціле число (1 \le N \le 10^6) – довжина рядка . У другому рядку знаходиться рядок , що складається з маленьких букв англійського алфавіту.

Output

Виведіть одне число – максимальну кількість балів, яку можна отримати при проходженні випробування.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

Ця задача складається з п'яти підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі, а також всі тести всіх необхідних для неї підзадач. Необхідні підзадачі також вказані в таблиці.

№ підзадачі

Бали

Обмеження

Примітка

0

0

Тести з умови

1

20

1 \le N \le 15

2

20

1 \le N \le 1000

Необхідні підзадачі: 1.

3

10

1 \le N \le 10^6; може містити лише символ «a» та «b»

Необхідні підзадачі: 0, 1, 2.

4

20

1 \le N \le 10^5

Необхідні підзадачі: 1, 2.

5

30

1 \le N \le 10^6

Необхідні підзадачі: 1, 2, 3, 4.