{"problem":{"name":"F. Библиотека","description":{"content":"Прошел почти год с момента, как Рик оказался на Флорине, однако его сознание никак не прояснялось. Воспоминания о прошлом были спрятаны в глубинах его разума, а может и вовсе утеряны. Однако сегодня ч","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10220F"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nЗадана строка $s$, состоящая из строчных латинских букв $(| s | <= 2500)$.\n\n## Выходные Данные\n\nВыведите одно число — количество искомых пар подстрок.\n\n## Пример\n\nВходные данныеabac\nВыходные данные9\n\n## Примечание\n\nРассмотрим подстроки длины $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$ искомых пар подстрок.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10220F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}