Однобуквенный палиндром
Совершенно недавно компания по разработке компьютерных игр "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 однобуквенного палиндрома. Гарантируется, что решение существует.