eolymp
bolt
Try our new interface for solving problems
Problems

Однобуквенный палиндром

Однобуквенный палиндром

Time limit 1 second
Memory limit 128 MiB

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

Игра начинается с того, что игроку выдается строка S, состоящая из N символов на родном языке пользователя. После чего пользователь за некоторое количество ходов должен получить из заданной строки строку, являющуюся однобуквенным палиндромом. За один ход игрок может поменять в строке местами два рядом стоящих символа.

Рисунок №1. Примеры однобуквенных палиндромов.

Строка S называется однобуквенным палиндромом, если существует такое натуральное число i, 1 ≤ iN, что S_i = S’_i, где S^{’}_1^{ }= S_N_{, }S^{’}_2^{ }= S_N_{-1}, …. S^{’}_N^{ }= S_1_{. }Строка S^{’} называется "обратной" строке S.

Рисунок №1.Описание второго примера, последовательность из двух ходов.

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

Input data

Первая строка входного файла содержит одно целое число N (2N250000).

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

Output data

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

Examples

Input example #1
4
97 122 97 122
Output example #1
1