Бухгалтер Валерий разбирается с нестыковками в бухгалтерских отчетах. Ему осталось проверить ровно $$$n$$$ документов, $$$i$$$-й из которых доступен в корпоративной сети по шестизначному целочисленному идентификатору $$$a_i$$$.
Назовем инверсией в $$$k$$$-м разряде пару номеров $$$i$$$ и $$$j$$$ такую, что $$$i \lt j$$$, и $$$k$$$-я цифра числа $$$a_i$$$ строго больше $$$k$$$-й цифры числа $$$a_j$$$. Тогда сложностью массива шестизначных чисел $$$\{a_i\}$$$ назовем суммарное количество инверсий во всех шести разрядах.
Валерий знает, что чем меньше сложность набора идентификаторов, тем меньше времени он потратит на вбивание их в адресную строку. Поскольку множество документов фиксировано, а радикально менять порядок проверки опасно (можно случайно пропустить некоторые документы), единственный доступный Валерию способ изменить исходный порядок проверки — сдвинуть его по циклу на несколько позиций. Напомним, что циклическим сдвигом массива $$$a_1, a_2, \ldots, a_n$$$ на $$$t$$$ позиций влево называется массив $$$a_{t+1}, a_{t+2}, \ldots, a_n, a_1, a_2, \ldots, a_t$$$.
Помогите Валерию выбрать циклический сдвиг исходного массива идентификаторов с минимальной сложностью.
В первой строке ввода дано целое число $$$n$$$ — количество документов, которые требуется проверить ($$$1 \leqslant n \leqslant 100\,000$$$).
В $$$i$$$-й из следующих $$$n$$$ строк даны шесть цифр — идентификатор $$$a_i$$$. Гарантируется, что все $$$a_i$$$ различны. Идентификаторы могут начинаться с нуля.
Выведите единственное целое число — минимальную из сложностей циклических сдвигов массива идентификаторов документов.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 17 | $$$n \leqslant 50$$$ | первая ошибка | |
| 2 | 19 | $$$n \leqslant 300$$$ | 1 | первая ошибка |
| 3 | 26 | $$$n \leqslant 1\,000$$$ | 1, 2 | первая ошибка |
| 4 | 38 | Без дополнительных ограничений | 1–3 | первая ошибка |
3 277659 177013 314836
4
3 250401 185217 296632
3
В первом примере выгодно сделать сдвиг на одну позицию влево, тогда число $$$177013$$$ окажется на первом месте. В таком случае в первых четырех разрядах будет по одной инверсии, а в последних двух — ноль.
Во втором примере порядок чисел уже оптимален с тремя инверсиями: по одной в первом, четвертом и шестом разрядах.
| Название |
|---|


