← К соревнованиям

Индивидуальная олимпиада по информатике и программированию

Шестизначные документы

Сложность: 46%

Бухгалтер Валерий разбирается с нестыковками в бухгалтерских отчетах. Ему осталось проверить ровно nn документов, ii-й из которых доступен в корпоративной сети по шестизначному целочисленному идентификатору aia_i.

Назовем инверсией в kk-м разряде пару номеров ii и jj такую, что i<ji < j, и kk-я цифра числа aia_i строго больше kk-й цифры числа aja_j. Тогда сложностью массива шестизначных чисел {ai}\{a_i\} назовем суммарное количество инверсий во всех шести разрядах.

Валерий знает, что чем меньше сложность набора идентификаторов, тем меньше времени он потратит на вбивание их в адресную строку. Поскольку множество документов фиксировано, а радикально менять порядок проверки опасно (можно случайно пропустить некоторые документы), единственный доступный Валерию способ изменить исходный порядок проверки – сдвинуть его по циклу на несколько позиций. Напомним, что циклическим сдвигом массива a1,a2,,ana_1, a_2, \ldots, a_n на tt позиций влево называется массив at+1,at+2,,an,a1,a2,,ata_{t+1}, a_{t+2}, \ldots, a_n, a_1, a_2, \ldots, a_t.

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

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

В первой строке ввода дано целое число nn – количество документов, которые требуется проверить (1n1000001 \leqslant n \leqslant 100\,000).

В ii-й из следующих nn строк даны шесть цифр – идентификатор aia_i. Гарантируется, что все aia_i различны. Идентификаторы могут начинаться с нуля.

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

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

Подзадачи

баллынеобх. подзадачиограничения
1

17

-

n50n \le 50

2

19

1

n300n \le 300

3

26

1, 2

n1000n \le 1000

4

38

1, 2, 3

Нет дополнительных ограничений

STDINSTDOUT
3
277659
177013
314836
4
3
250401
185217
296632
3

Примечание

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

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