408927: GYM103382 5 Древнее имя

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

5. Древнее имяограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.

Катя так восхитилась данным способом, что сразу же захотела подсчитать древность своего любимого индейского имени.

Входные данные

В первой строке входных данных содержится целое число $$$N$$$ $$$\left(1 \le N \le 10^{5} \right)$$$ — длина любимого индейского имени Кати.

Во второй строке содержится последовательность из $$$N$$$ строчных букв английского алфавита — любимое индейское имя Кати.

Выходные данные

Выведите единственное целое число — коэффициент древности имени.

Обратите внимание, что при данных ограничениях ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Система оценки

В этой задаче 30 тестов, не считая теста из условия. Каждый тест будет оценён независимо.

На тесты наложены следующие ограничения:

Номера тестовБаллов за тестДополнительные ограничения
10Тест из условия
2 – 112$$$N \le 10^3$$$
12 – 162в имени есть только буквы «a» и «b»
17 – 212все буквы имени записаны по возрастанию их номеров в алфавите
22 – 316без дополнительных ограничений
ПримерВходные данные
7
osceola
Выходные данные
6
Примечание

В примере из условия шесть подходящих пар: символы «o» и «s» на первой и второй позиции, символы «c» и «e» на третьей и четвёртой позициях, символы «с» и «o» на третьей и пятой позициях, символы «e» и «o» на четвёртой и пятой позициях, символы «с» и «l» на третьей и шестой позициях, символы «e» и «l» на четвёртой и шестой позициях соответственно.

加入题单

上一题 下一题 算法标签: