ИОИП: Заключительный этап ИОИП 2021

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

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