Однобуквенный палиндром
Однобуквенный палиндром
Совершенно недавно компания по разработке компьютерных игр "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 необходимо определить минимальное количество ходов, необходимых для получения из данной строки однобуквенного палиндрома.
Input data
Первая строка входного файла содержит одно целое число N (2 ≤ N ≤ 250000).
Вторая строка входного файла описывает строку S и содержит N целых чисел от 1 до 65535 разделенных одиночными пробелами. Каждое число представляет собой код соответствующего символа в строке. Символы считаются равными, если равны соответствующие им коды.
Output data
Выходной файл должен содержать одно число – минимальное количество ходов, необходимых для получения из заданной строки S однобуквенного палиндрома. Гарантируется, что решение существует.
Examples
4 97 122 97 122
1