Problem F
Freestyle Masonry


Maybe he should have made a plan before starting to build the wall, but now it is too late. Fred only has a bunch of $2\times 1$ bricks left and wants to finish the wall. Can he still complete it with the remaining $2\times 1$ bricks? Note that the wall to be built should have a width of exactly $w$ units and a height of exactly $h$ units.
Input
The input consists of:
-
One line with two integers $w$ and $h$ ($1\leq w\leq 2\cdot 10^5$, $1\leq h\leq 10^6$), the width and height of the wall Fred wants to build.
-
One line with $w$ integers $h_1,\dots ,h_n$ ($0\leq h_i\leq 10^6$), where $h_i$ is the current height of the wall at position $i$.
Output
Output “possible” if Fred can complete his wall and “impossible” otherwise.
Sample Input 1 | Sample Output 1 |
---|---|
3 3 0 0 1 |
possible |
Sample Input 2 | Sample Output 2 |
---|---|
6 3 1 0 1 1 0 1 |
possible |
Sample Input 3 | Sample Output 3 |
---|---|
6 2 1 0 1 1 0 1 |
impossible |
Sample Input 4 | Sample Output 4 |
---|---|
5 2 1 2 3 2 2 |
impossible |