Однобуквений паліндром
Нещодавно компанія з розробки комп'ютерних ігор "GoldSilver Software" випустила нову гру для смартфонів під назвою "Однобуквений паліндром". Гра виявилася дуже простою, тому швидко здобула популярність.
Гра починається з того, що гравцеві надається рядок S, що складається з N символів рідною мовою користувача. Завдання гравця — за певну кількість ходів перетворити цей рядок на однобуквений паліндром. За один хід гравець може поміняти місцями два сусідні символи в рядку.
Рисунок №1. Приклади однобуквених паліндромів.
Рядок S називається однобуквеним паліндромом, якщо існує таке натуральне число i, 1 ≤ i ≤ N, що S_i = S’_i, де S’_1 = S_N, S’_2 = S_N-1, ..., S’_N = S_1. Рядок S’ називається "оберненим" рядком S.
Рисунок №1. Опис другого прикладу, послідовність з двох ходів.
Для заданого рядка S потрібно визначити мінімальну кількість ходів, необхідних для перетворення його на однобуквений паліндром.
Вхідні дані
Перша строка вхідного файлу містить одне ціле число N (2 ≤ N ≤ 250000).
Друга строка вхідного файлу описує рядок S і містить N цілих чисел від 1 до 65535, розділених одиночними пробілами. Кожне число представляє код відповідного символу в рядку. Символи вважаються рівними, якщо рівні їхні коди.
Вихідні дані
Вихідний файл повинен містити одне число — мінімальну кількість ходів, необхідних для перетворення заданого рядка S на однобуквений паліндром. Гарантується, що рішення існує.