Freestyle Masonry

Interview

Time limit2sMemory limit1024 MB

Summary

Given the current column heights of a w by h wall, decide whether the empty cells can be filled exactly with 2x1 bricks.

Level: Medium6 of 10
Topics: Sorting, Array, Implementation
Solved: No attempts yet

Problem

Fred got a simple task. He just has to build a $w\times h$ wall. To make this easier, he was given enough $2\times1$ bricks and a few $1\times1$ bricks to complete the wall. Fred did not think this task would be hard, so he started building the wall without planning the design. He only noticed the problem when he ran out of $1\times1$ bricks.

Figure F.1: Visualization of Sample Input 2. The red bricks have already been placed by Fred. The blue bricks still need to be placed to complete the wall (the only possible design in this case).

Fred has only $2\times1$ bricks left, and he wants to finish the wall with them. Can he still complete the wall using only the remaining $2\times1$ bricks? The wall must have a width of exactly $w$ units and a height of exactly $h$ units.

Input

The first line contains two integers $w$ and $h$ ( $1\leq w\leq2\cdot10^5$ , $1\leq h\leq10^6$ ), the width and height of the wall Fred wants to build.

The second line contains $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 the wall, and impossible otherwise.

Examples4

Example 1
Input
```
3 3
0 0 1
```
Expected output
```
possible
```
Example 2
Input
```
6 3
1 0 1 1 0 1
```
Expected output
```
possible
```
Example 3
Input
```
6 2
1 0 1 1 0 1
```
Expected output
```
impossible
```
Example 4
Input
```
5 2
1 2 3 2 2
```
Expected output
```
impossible
```