시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 172 | 41 | 33 | 22.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:
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.
This subtask has an additional constraint:
This subtask has an additional constraint:
This subtask has no additional constraints.
3 1 2 3
1
3 1 3 2
0