자유 벽돌 쌓기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

w×h 벽의 열별 현재 높이가 주어질 때, 비어 있는 칸을 2×1 벽돌로 빈틈없이 채울 수 있는지 판단합니다.

난이도: 보통10점 중 6점
유형: 정렬, 배열, 구현
정답자: 아직 제출이 없습니다

문제

Fred는 간단한 일을 맡았다. 그는 $w\times h$ 크기의 벽을 쌓기만 하면 된다. 일을 쉽게 하려고 $2\times1$ 벽돌이 충분히 주어졌고, 벽을 완성할 $1\times1$ 벽돌도 몇 개 주어졌다. Fred는 이 일이 어렵지 않을 것이라 생각하고 설계를 따로 세우지 않은 채 벽을 쌓기 시작했다. $1\times1$ 벽돌이 떨어지고 나서야 그는 이 방식이 잘못되었음을 알았다.

그림 F.1: 입력 예제 2의 시각화. 빨간 벽돌은 Fred가 이미 놓은 것이다. 파란 벽돌은 벽을 완성하려면 아직 놓아야 하며, 이 경우 가능한 배치는 이것 하나뿐이다.

Fred에게는 이제 $2\times1$ 벽돌만 남아 있고, 그는 이것으로 벽을 마무리하려 한다. 남은 $2\times1$ 벽돌만으로 벽을 완성할 수 있을까? 벽의 너비는 정확히 $w$ 단위, 높이는 정확히 $h$ 단위여야 한다.

입력

첫 줄에 Fred가 쌓으려는 벽의 너비와 높이를 뜻하는 두 정수 $w$ 와 $h$ 가 주어진다 ( $1\leq w\leq2\cdot10^5$ , $1\leq h\leq10^6$ ).

둘째 줄에는 $w$ 개의 정수 $h_1,\dots,h_n$ 이 주어진다 ( $0\leq h_i\leq 10^6$ ). $h_i$ 는 위치 $i$ 에서 벽의 현재 높이다.

출력

Fred가 벽을 완성할 수 있으면 possible을, 그렇지 않으면 impossible을 출력한다.

예제4

예제 1
입력
```
3 3
0 0 1
```
예상 출력
```
possible
```
예제 2
입력
```
6 3
1 0 1 1 0 1
```
예상 출력
```
possible
```
예제 3
입력
```
6 2
1 0 1 1 0 1
```
예상 출력
```
impossible
```
예제 4
입력
```
5 2
1 2 3 2 2
```
예상 출력
```
impossible
```