Паліндром з однієї літери#3031

Паліндром з однієї літери

1 секунда

128 мегабайтів

Середня

Нещодавно компанія з розробки комп'ютерних ігор Gold&Silver Software випустила нову гру для смартфонів під назвою Паліндром з однієї літери. Простота гри швидко зробила її популярною.

Гра починається з того, що гравцеві дається рядок $S$ , який складається з $N$ символів. Мета – перетворити цей рядок на паліндром з однієї літери за певну кількість ходів. За кожен хід гравець може поміняти місцями два сусідні символи у рядку.

Рис. 1. Приклади паліндромів з однієї літери.

Рядок $S$ вважається паліндромом з однієї літери, якщо існує натуральне число $i$ ( $1 \leq i \leq N$ 1 \leq i \leq N), таке що $S_{i} = S_{i}^{'}$ S_i = S'_i, де $S_{1}^{'} = S_{N}$ S'_1 = S_N, $S_{2}^{'} = S_{N - 1}$ S'_2 = S_{N-1}, ..., $S_{N}^{'} = S_{1}$ S'_N = S_1. Рядок $S^{'}$ S' називається "оберненим" до рядка $S$ .

Рис. 2. Опис другого прикладу, послідовність з двох ходів.

Для заданого рядка $S$ визначте мінімальну кількість ходів, необхідних для отримання паліндрому з однієї літери.

Вхідні дані

Перший рядок вхідних даних містить одне ціле число $N$ ( $2 \leq N \leq 250000$ 2 \leq N \leq 250000).

Другий рядок містить $N$ цілих чисел, розділених пробілами, кожне з яких знаходиться в межах від $1$ до $65535$ . Кожне число є кодом відповідного символу у рядку. Символи вважаються однаковими, якщо їхні коди збігаються.

Вихідні дані

Виведіть одне число — мінімальну кількість ходів, необхідних для перетворення заданого рядка $S$ на паліндром з однієї літери. Гарантується, що розв'язок існує.

Приклади

Приклад 1