Чому корова перейшла дорогу (Платина)

Фермер Джон розводить $n$ порід корів, і кожне його поле призначене для випасу корів лише однієї певної породи. Наприклад, поле, призначене для породи $12$, може використовуватися лише коровами породи $12$, але не коровами будь-яких інших порід.

Через ферму Фермера Джона проходить довга дорога. З одного боку дороги розташована послідовність із $n$ полів — по одному для кожної породи, а з іншого боку знаходиться ще одна послідовність із $n$ полів, також по одному для кожної породи. Коли корова переходить через дорогу, вона переміщується між двома полями, призначеними для її породи.

Якби Фермер Джон заздалегідь усе ретельно спланував, він розташував би поля в однаковому порядку по обидва боки дороги, так щоб два поля для кожної породи знаходилися прямо навпроти одне одного. У такому випадку корови могли б переходити через дорогу, не перетинаючись із коровами інших порід. На жаль, порядок полів по обидва боки дороги може відрізнятися, тому деякі пари порід можуть мати шляхи, що перетинаються. Пара різних порід $(a,b)$ називається «парою, що перетинається», якщо будь-який можливий шлях через дорогу для породи $a$ обов'язково перетинає будь-який можливий шлях через дорогу для породи $b$.

Фермер Джон хоче мінімізувати кількість пар порід, що перетинаються. З організаційних причин він може переставляти поля на одному боці дороги за допомогою «циклічного зсуву». Тобто для деякого 0 \le k < n кожне поле зсувається на $k$ позицій вперед, при цьому поля, що знаходилися на останніх $k$ позиціях, переміщуються на перші $k$ позицій.

Наприклад, якщо поля з одного боку дороги спочатку розташовані за породами в порядку 3, 7, 1, 2, 5, 4, 6 і виконується циклічний зсув на k = 2, новий порядок буде 4, 6, 3, 7, 1, 2, 5.

Визначте мінімально можливу кількість пар порід, що перетинаються, після виконання відповідного циклічного зсуву полів на одному боці дороги.