{"raw_statement":[{"iden":"statement","content":"Прошел почти год с момента, как Рик оказался на Флорине, однако его сознание никак не прояснялось. Воспоминания о прошлом были спрятаны в глубинах его разума, а может и вовсе утеряны. Однако сегодня что-то случилось. Рик вспомнил: у него была работа. Он анализировал Ничто. Наверное, Ничто — это космос, а значит Рик в прошлом был космоаналитиком. А еще Рик вспомнил, что все жители Флорины должны были погибнуть, но он не знал, почему. \n\nРезидента Мирлина Теренса заинтересовала эта информация, поэтому он взял Рика с собой в библиотеку Верхнего города. Может быть, какая-нибудь литература по космоанализу могла бы вернуть ему память? Теренс не знал, что пропавшего космоаналитика активно ищут, а потому в библиотеке был получен приказ сообщать о любых посетителях, которые спросят о такой литературе. Библиотекарь отследил запросы наших героев в поисковой системе и поспешил вызвать патрульных.\n\nТем временем Теренс предложил Рику ознакомиться с книгой известного автора Врийта \"Трактат об инструментальном космоанализе\". Рику книга определенно показалось знакомой, особенно его привлекла строка $s$. Смысла самой строки, он, к сожалению, не понимал, однако в ее частях он видел что-то знакомое. Чтобы разобраться подробнее, Рик решил изучить все подстроки $s$. Однако изучать равные подстроки не было смысла, а остальные стоило как-либо систематизировать. Например, расставить их по длине и в алфавитном порядке. Поэтому Рик попросил вас узнать, сколько у данной строки существует пар подстрок $s_1$ и $s_2$ равной длины, таких, что $s_1 < s_2$ лексикографически.\n\nЗадана строка $s$, состоящая из строчных латинских букв $(| s | <= 2500)$.\n\nВыведите одно число — количество искомых пар подстрок.\n\nРассмотрим подстроки длины $1$. Имеется две подстроки \"$a$\", каждая из которых меньше подстрок \"$b$\" и \"$c$\". Также подстрока \"$b$\" меньше подстроки \"$c$\". Отсюда получаем $5$ пар искомых подстрок.\n\nТеперь рассмотрим подстроки длины $2$. Подстрока \"$a b$\" меньше подстрок \"$b a$\" и \"$a c$\", а строка \"$a c$\" меньше, чем строка \"$b a$\". Отсюда получаем еще $3$ пары.\n\nНаконец, рассмотрим подстроки длины $3$. Подстрока \"$a b a$\" меньше подстроки \"$b a c$\".\n\nТаким образом, суммарно получаем $9$ искомых пар подстрок.\n\n"},{"iden":"входные данные","content":"Задана строка $s$, состоящая из строчных латинских букв $(| s | <= 2500)$."},{"iden":"выходные данные","content":"Выведите одно число — количество искомых пар подстрок."},{"iden":"пример","content":"Входные данныеabac\nВыходные данные9\n"},{"iden":"примечание","content":"Рассмотрим подстроки длины $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$ искомых пар подстрок."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the maximum trip length.  \nLet $ 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.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 250000 $  \n2. $ 1 \\leq l_i, d_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, 2N\\} $\n\n**Objective**  \nFor 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:  \n$$\n\\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)\n$$  \nOutput $ \\text{Cost}(1), \\text{Cost}(2), \\dots, \\text{Cost}(N) $.","simple_statement":"You are given N. There are 2N meals: N for lunch and N for dinner, each with a price.  \nFor each i from 1 to N, you must choose i lunch meals and i dinner meals (no repeats), so that the total cost is minimized.  \nPrint the minimum total cost for each i = 1, 2, ..., N.","has_page_source":false}