시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB172413322.603%

문제

You are given an array of non-negative integers $a_1, a_2, \dots, a_N$.

You can perform the following operation several times:

  • Choose an index $i$. ($1 \leq i <$ length of the array) Then, remove $a_i, a_{i+1}$ and replace them with $a_i \oplus a_{i+1}$. (The total length of the array decreases by 1)

Expression $x \oplus y$ means bitwise xor of two numbers $x$ and $y$. In binary representation, if the $i$-th digit of x and y is equal, then the $i$-th digit of $x \oplus y$ is $0$, and if not, it is $1$.

The given operation exists in all modern programming languages. For example, in C++ and Java, it is represented as $x\ ^{\wedge}\ y$.

You want to convert the given array into a zig-zag array.

We say an array of $m$ integers, $z_1, z_2, ..., z_{m}$, is a zig-zag array if no three consecutive elements in the array are either monotonically increasing or monotonically decreasing.

In other words, if there are three elements $z_i, z_{i+1}, z_{i+2}$ in the array such that $z_i \leq z_{i+1} \leq z_{i+2}$ or $z_i \geq z_{i+1} \geq z_{i+2}$, the array is not zig-zag. Otherwise, it is zig-zag array.

Find the minimum number of operations needed to convert $\{a_i\}$ into a zig-zag array.

입력

The first line contains an integer $N$, where $N$ denotes the length of the sequence.

The second line contains $N$ space-separated non-negative integers $a_1, a_2, \dots, a_N$.

출력

Print the minimum number of operations needed to change the sequence $\{a_i\}$ into a zig-zag array.

제한

  • $1 \leq N \leq 3\,000$
  • $0 \leq a_i < 2^{30}$ $(1 \le i \le N)$

서브태스크 1 (20점)

This subtask has an additional constraint:

  • $N \le 20$

서브태스크 2 (30점)

This subtask has an additional constraint:

  • $N \le 100$

서브태스크 3 (50점)

This subtask has no additional constraints.

예제 입력 1

3
1 2 3

예제 출력 1

1

예제 입력 2

3
1 3 2

예제 출력 2

0

출처

University > KAIST > 2022 KAIST RUN Spring Contest D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.