28774번 - Шестизначные документы 다국어

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

Назовем инверсией в $k$-м разряде пару номеров $i$ и $j$ такую, что $i < 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$ различны. Идентификаторы могут начинаться с нуля.

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

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

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