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