지그재그 수열

길이 $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$가 된다.