В Ужляндії знову щось трапилось! Сьогодні відзначає свій день посвяти у лицарі Головний Ужляндський Дитар – Маша. За традицією їй задали Головний Ужляндський Рядок довжини , що складається з маленьких букв англійського алфавіту. Символи рядка пронумеровані від 1 до .
Щоб пройти порічне випробування, Маші необхідно дістатися останнього елементу рядка, отриманими максимальну кількість балів. Правила випробування та нарахування балів такі:
Початкова позиція лицаря – елемент рядка з номером 1;
Лицар може перейти від позиції з номером до позиції з номером за умови 1 \leqslant j < i \leqslant N. За такий перехід він отримає (i - j) \cdot |S_i - S_j| балів, де |S_i - S_j| позначає різницю між позиціями цих символів у алфавіті;
Кінцева позиція – елемент рядка з номером .
На жаль, журі випробування не знає яку ж насправді максимальну кількість балів можна отримати. Саме тому воно доручило Вам знайти це значення.
У першому рядку вхідного файлу знаходиться одне ціле число (1 \le N \le 10^6) – довжина рядка . У другому рядку знаходиться рядок , що складається з маленьких букв англійського алфавіту.
Виведіть одне число – максимальну кількість балів, яку можна отримати при проходженні випробування.
Example 1
Example 2
Ця задача складається з п'яти підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі, а також всі тести всіх необхідних для неї підзадач. Необхідні підзадачі також вказані в таблиці.
№ підзадачі | Бали | Обмеження | Примітка |
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. |