C. Шестизначные документы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бухгалтер Валерий разбирается с нестыковками в бухгалтерских отчетах. Ему осталось проверить ровно $$$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$$$ различны. Идентификаторы могут начинаться с нуля.

Выходные данные

Выведите единственное целое число — минимальную из сложностей циклических сдвигов массива идентификаторов документов.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
117$$$n \leqslant 50$$$первая ошибка
219$$$n \leqslant 300$$$1первая ошибка
326$$$n \leqslant 1\,000$$$1, 2первая ошибка
438Без дополнительных ограничений1–3первая ошибка
Примеры
Входные данные
3
277659
177013
314836
Выходные данные
4
Входные данные
3
250401
185217
296632
Выходные данные
3
Примечание

В первом примере выгодно сделать сдвиг на одну позицию влево, тогда число $$$177013$$$ окажется на первом месте. В таком случае в первых четырех разрядах будет по одной инверсии, а в последних двух — ноль.

Во втором примере порядок чисел уже оптимален с тремя инверсиями: по одной в первом, четвертом и шестом разрядах.