Задача №111133. Однобуквенный палиндром

Совершенно недавно компания по разработке компьютерных игр «Gold&Silver Software» выпустила новую игру для смартфонов под названием «Однобуквенный палиндром». Игра получилась очень простая, поэтому быстро стала популярной.

Игра начинается с того, что игроку выдается строка S, состоящая из N символов на родном языке пользователя. После чего пользователь за некоторое количество ходов должен получить из заданной строки строку, являющуюся однобуквенным палиндромом. За один ход игрок может поменять в строке местами два рядом стоящих символа. Строка S называется однобуквенным палиндромом, если существует такое натуральное число i, 1 ≤ i ≤ N, что Si = Ri, где R1 = SN, R2 = SN - 1, ..., RN = S1. Строка R называется «обратной» строке S.

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

Входные данные

Первая строка входных данных содержит одно целое число N (2 ≤ N ≤ 250 000). Вторая строка описывает строку S и содержит N целых чисел от 1 до 65535, разделенных одиночными пробелами. Каждое число представляет собой код соответствующего символа в строке. Символы считаются равными, если равны соответствующие им коды.

Выходные данные

Выходные данные должны содержать одно число — минимальное количество ходов, необходимых для получения из заданной строки S однобуквенного палиндрома. Гарантируется, что решение существует.

Примеры тестов

Входные данные
4
97 122 97 122
Выходные данные
1
Входные данные
6
115 121 115 116 101 109
Выходные данные
3
Входные данные
6
116 117 114 116 108 101
Выходные данные
2

Подзадача 1.
\(1 \le N \le 300\). Решение оценивается в \(30\) баллов.
Подзадача 2.
\(1 \le N \le 5\,000\). Решение оценивается в \(30\) баллов.
Подзадача 3.
Дополнительные ограничения отсутствуют. Решение оценивается в \(40\) баллов.

Сдать: для сдачи задач необходимо войти в систему