Прошел почти год с момента, как Рик оказался на Флорине, однако его сознание никак не прояснялось. Воспоминания о прошлом были спрятаны в глубинах его разума, а может и вовсе утеряны. Однако сегодня что-то случилось. Рик вспомнил: у него была работа. Он анализировал Ничто. Наверное, Ничто — это космос, а значит Рик в прошлом был космоаналитиком. А еще Рик вспомнил, что все жители Флорины должны были погибнуть, но он не знал, почему.
Резидента Мирлина Теренса заинтересовала эта информация, поэтому он взял Рика с собой в библиотеку Верхнего города. Может быть, какая-нибудь литература по космоанализу могла бы вернуть ему память? Теренс не знал, что пропавшего космоаналитика активно ищут, а потому в библиотеке был получен приказ сообщать о любых посетителях, которые спросят о такой литературе. Библиотекарь отследил запросы наших героев в поисковой системе и поспешил вызвать патрульных.
Тем временем Теренс предложил Рику ознакомиться с книгой известного автора Врийта "Трактат об инструментальном космоанализе". Рику книга определенно показалось знакомой, особенно его привлекла строка $s$. Смысла самой строки, он, к сожалению, не понимал, однако в ее частях он видел что-то знакомое. Чтобы разобраться подробнее, Рик решил изучить все подстроки $s$. Однако изучать равные подстроки не было смысла, а остальные стоило как-либо систематизировать. Например, расставить их по длине и в алфавитном порядке. Поэтому Рик попросил вас узнать, сколько у данной строки существует пар подстрок $s_1$ и $s_2$ равной длины, таких, что $s_1 < s_2$ лексикографически.
Задана строка $s$, состоящая из строчных латинских букв $(| s | <= 2500)$.
Выведите одно число — количество искомых пар подстрок.
Рассмотрим подстроки длины $1$. Имеется две подстроки "$a$", каждая из которых меньше подстрок "$b$" и "$c$". Также подстрока "$b$" меньше подстроки "$c$". Отсюда получаем $5$ пар искомых подстрок.
Теперь рассмотрим подстроки длины $2$. Подстрока "$a b$" меньше подстрок "$b a$" и "$a c$", а строка "$a c$" меньше, чем строка "$b a$". Отсюда получаем еще $3$ пары.
Наконец, рассмотрим подстроки длины $3$. Подстрока "$a b a$" меньше подстроки "$b a c$".
Таким образом, суммарно получаем $9$ искомых пар подстрок.
## Входные Данные
Задана строка $s$, состоящая из строчных латинских букв $(| s | <= 2500)$.
## Выходные Данные
Выведите одно число — количество искомых пар подстрок.
## Пример
Входные данныеabac
Выходные данные9
## Примечание
Рассмотрим подстроки длины $1$. Имеется две подстроки "$a$", каждая из которых меньше подстрок "$b$" и "$c$". Также подстрока "$b$" меньше подстроки "$c$". Отсюда получаем $5$ пар искомых подстрок.Теперь рассмотрим подстроки длины $2$. Подстрока "$a b$" меньше подстрок "$b a$" и "$a c$", а строка "$a c$" меньше, чем строка "$b a$". Отсюда получаем еще $3$ пары.Наконец, рассмотрим подстроки длины $3$. Подстрока "$a b a$" меньше подстроки "$b a c$".Таким образом, суммарно получаем $9$ искомых пар подстрок.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the maximum trip length.
Let $ M = \{ (l_i, d_i) \mid i \in \{1, \dots, 2N\} \} $ be the set of $ 2N $ menu pairs, where $ l_i $ and $ d_i $ are the lunch and dinner prices of menu $ i $, respectively.
**Constraints**
1. $ 1 \leq N \leq 250000 $
2. $ 1 \leq l_i, d_i \leq 10^9 $ for all $ i \in \{1, \dots, 2N\} $
**Objective**
For each $ i \in \{1, \dots, N\} $, find the minimum total cost to select $ i $ distinct menus for lunch and $ i $ distinct menus for dinner (with no menu used for both lunch and dinner), i.e., choose two disjoint subsets $ L, D \subseteq \{1, \dots, 2N\} $, each of size $ i $, such that:
$$
\text{Cost}(i) = \min_{\substack{L, D \subseteq \{1,\dots,2N\} \\ |L|=|D|=i \\ L \cap D = \emptyset}} \left( \sum_{j \in L} l_j + \sum_{j \in D} d_j \right)
$$
Output $ \text{Cost}(1), \text{Cost}(2), \dots, \text{Cost}(N) $.