압축기
시간 제한3초메모리 제한256 MB
각 단계에서 길이 n인 수열을 길이 ceil(n/2)인 수열로 줄이는데, 각 새 원소는 대응하는 양 끝 후보 중 하나를 고른다. 두 후보가 다를 때마다 벌점이 발생하며, 전체 벌점의 최솟값을 구한다.
문제
Вася는 텍스트를 압축하는 완전히 새로운 방법을 고안했다. 그는 이 방법이 중국어처럼 알파벳이 큰 언어에서 특히 잘 동작한다고 생각한다. 그래서 Вася는 텍스트를 문자 코드의 수열 a1, a2, …, an으로 표현한다.
압축 알고리즘은 여러 단계로 나뉜다. 각 단계마다 길이가 절반인 새로운 수열 b1, b2, …, b⌈n/2⌉을 만든다. 이때 bi는 ai 또는 *a**n–i+*1 중 하나가 될 수 있다. 선택은 압축기에 맡겨진다. 그런 다음 원래 수열을 새 수열로 교체하고 다음 단계로 넘어간다. 수열의 길이가 1이 되면 과정이 끝난다.
Вася는 모호한 경우(ai ≠ *a**n–i+*1)에는 정보 손실을 막기 위해 추가 데이터를 저장해야 한다는 점을 알아냈다. 또한 현재 단계에서 어떤 문자를 고르는지에 따라 이후에 모호함이 생길지 여부가 달라질 수 있다.
알고리즘의 효율성을 평가하기 위해 Вася는 압축 과정에서 생기는 모호함마다 벌점 1점을 매기기로 했다. 안타깝게도 Вася는 모호함이 생길 때 어떻게 선택해야 할지 떠올리지 못해 여러분에게 도움을 청했다. 그는 주어진 수열을 압축할 때 모호함을 최적으로 해결하여 얻을 수 있는 최소 총 벌점을 계산하는 프로그램을 작성해 달라고 부탁한다.
입력
첫째 줄에는 정수 n이 주어진다 (1 ≤ n ≤ 200000). 둘째 줄에는 원래 수열인 n개의 정수 a1, a2, …, an이 주어진다 (1 ≤ ai ≤ 109).
출력
주어진 수열을 설명한 알고리즘으로 압축할 때 얻을 수 있는 최소 총 벌점을 정수로 출력한다.