408927: GYM103382 5 Древнее имя
Description
Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.
Катя так восхитилась данным способом, что сразу же захотела подсчитать древность своего любимого индейского имени.
Входные данныеВ первой строке входных данных содержится целое число $$$N$$$ $$$\left(1 \le N \le 10^{5} \right)$$$ — длина любимого индейского имени Кати.
Во второй строке содержится последовательность из $$$N$$$ строчных букв английского алфавита — любимое индейское имя Кати.
Выходные данныеВыведите единственное целое число — коэффициент древности имени.
Обратите внимание, что при данных ограничениях ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).
Система оценкиВ этой задаче 30 тестов, не считая теста из условия. Каждый тест будет оценён независимо.
На тесты наложены следующие ограничения:
Номера тестов | Баллов за тест | Дополнительные ограничения |
1 | 0 | Тест из условия |
2 – 11 | 2 | $$$N \le 10^3$$$ |
12 – 16 | 2 | в имени есть только буквы «a» и «b» |
17 – 21 | 2 | все буквы имени записаны по возрастанию их номеров в алфавите |
22 – 31 | 6 | без дополнительных ограничений |
7 osceolaВыходные данные
6Примечание
В примере из условия шесть подходящих пар: символы «o» и «s» на первой и второй позиции, символы «c» и «e» на третьей и четвёртой позициях, символы «с» и «o» на третьей и пятой позициях, символы «e» и «o» на четвёртой и пятой позициях, символы «с» и «l» на третьей и шестой позициях, символы «e» и «l» на четвёртой и шестой позициях соответственно.