22168번 - Архиватор 다국어

Вася придумал радикально новый способ сжатия текста. Он считает, что особенно хорошо его метод будет работать для языков с большим алфавитом, таких как китайский. По этой причине Вася представляет текст в виде последовательности кодов символов a₁, a₂, …, a_n.

Алгоритм сжатия разбит на фазы. На каждой фазе строится новая последовательность вдвое меньшей длины b₁, b₂, …, b_⌈n/2⌉. При этом b_i может равняться либо a_i, либо a_n–i+1. Выбор оставляется на усмотрение архиватора. После этого исходная последовательность заменяется новой, и алгоритм переходит к следующей фазе. Процесс завершается, когда длина последовательности становится равной единице.

Вася заметил, что в случае неоднозначности (a_i ≠ a_n–i+1) приходится сохранять дополнительные данные во избежание потери информации. Кроме того, от выбора символа на текущей фазе может зависеть наличие или отсутствие неоднозначностей в дальнейшем.

Для оценки эффективности алгоритма Вася решил назначать единицу штрафа за каждую неоднозначность, возникающую в процессе работы архиватора. К сожалению, Вася не смог придумать, каким образом нужно делать выбор при возникновении неоднозначностей, и обратился к вам за помощью. Он просит вас написать программу, которая вычислит минимальный возможный суммарный штраф при оптимальном разрешении неоднозначностей.

Первая строка содержит целое число n (1 ≤ n ≤ 200000). Вторая строка содержит исходную последовательность — n целых чисел a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁹).

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