34230번 - 지그재그 수열

문제

길이 $n$의 수열 $[a_{1},\cdots ,a_{n}]$이 지그재그 수열이라는 것은 다음 두 조건 중 하나를 만족하는 것이다.

• 모든 1ドル\leq i \leq n-1$에 대해, $i$가 짝수이면 $a_{i} < a_{i+1}$이고 $i$가 홀수이면 $a_{i} > a_{i+1}$
• 모든 1ドル\leq i \leq n-1$에 대해, $i$가 짝수이면 $a_{i} > a_{i+1}$이고 $i$가 홀수이면 $a_{i} < a_{i+1}$

길이가 1ドル$인 모든 수열은 지그재그 수열이다.

길이 $N$의 수열 $A$가 주어진다. 당신은 한 연산에서 수열 $A$에서 인접한 두 원소 $A_i$와 $A_{i+1}$을 골라 두 수를 수열에서 제거한 후, 그 자리에 두 수의 XOR을 넣을 수 있다.

$A$를 지그재그 수열로 만들기 위한 최소 연산 횟수를 출력하라.

입력

첫째 줄에 $N$이 주어진다. $(2 \leq N \leq 5,000円)$

둘째 줄에 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i \le 4,095円)$

출력

첫째 줄에 $A$를 지그재그 수열로 만들기 위한 최소 연산 횟수를 출력한다.

제한

노트

두 수의 XOR 연산은, 두 수를 이진수로 나타냈을 때 각 비트 자리에서 서로 다르면 1ドル,ドル 같으면 0ドル$이 되는 비트 연산이다. 예를 들어, 6ドル$과 4ドル$를 이진수로 나타내면 각각 110ドル_{(2)},ドル 100ドル_{(2)}$이 되고, 두 수를 XOR한 값은 010ドル_{(2)}$으로 2ドル$가 된다.