Чому корова перейшла дорогу (Платина)
Фермер Джон вирощує n порід корів, і кожне з його полів призначене для випасу однієї конкретної породи. Наприклад, поле для корів породи 12 може використовуватися лише для цієї породи і не підходить для інших. Уздовж ферми проходить довга дорога. З одного боку дороги розташовані n полів (по одному для кожної породи корів), і з іншого боку — ще n полів (також по одному для кожної породи). Коли корова перетинає дорогу, вона переходить з одного поля, призначеного для її породи, на інше поле, також призначене для цієї ж породи.
Якби Фермер Джон заздалегідь продумав розташування полів, він міг би розмістити їх так, щоб поля для однієї і тієї ж породи знаходилися прямо навпроти одне одного по різні боки дороги. У такому випадку корови не стикалися б при переході дороги. Однак, порядок полів з різних сторін дороги може відрізнятися, і тоді можуть виникати пари порід, шляхи яких перетинаються при переході дороги. Пара різних порід (a, b) вважається "перетинаючоюся", якщо будь-який шлях через дорогу для корови породи a перетинається з будь-яким шляхом для корови породи b.
Фермер Джон прагне мінімізувати кількість таких перетинаючих пар. З логістичних причин він може здійснити "циклічний зсув" полів на одній стороні дороги. Це означає, що для деякого 0 ≤ k < n, кожне поле зсувається на k позицій вперед, а поля з останніх k позицій переміщуються на початок. Наприклад, якщо поля на одній стороні дороги розташовані в порядку: 3, 7, 1, 2, 5, 4, 6 і виконується зсув на k = 2, то новий порядок буде: 4, 6, 3, 7, 1, 2, 5. Визначте мінімальну можливу кількість перетинаючих пар порід, які можуть існувати після відповідного циклічного зсуву полів на одній стороні дороги.
Вхідні дані
Перша строка містить число n (1 ≤ n ≤ 10^5). Наступні n строк описують порядок порід на полях вздовж першої сторони дороги. Кожен номер породи — ціле число в діапазоні від 1 до n. Останні n строк описують порядок порід на полях з іншої сторони дороги.
Вихідні дані
Виведіть мінімальну кількість перетинаючих пар порід корів після циклічного зсуву полів на одній стороні дороги (будь-яка сторона може зсуватися).