Apple Tree

Interview

Time limit1sMemory limit1024 MB

Summary

Given N target heights, decide whether a 1-unit and a 2-unit watering can, used simultaneously on trees (or together on one tree), can reach exactly those heights.

Level: Medium5 of 10
Topics: Greedy, Math, Implementation, Array
Solved: No attempts yet

Problem

Iha recently bought apple tree seeds and planted them in a row in the backyard of the farm, numbered $1$ through $N$ . All of these trees start with height $0$ .

To grow the apple trees well, Iha prepared $2$ watering cans. One watering can grows a single tree by $1$ , and the other grows a single tree by $2$ . These watering cans must be used at the same time, and a watering can cannot be used on soil with no tree. Both watering cans may be used on one tree to grow it by $3$ .

After programming the entire watering can management system, Iha was about to grow the apple trees. Just then, Gapeun came to visit and said he would like each apple tree to have a certain height. Now Iha started to worry a little, because it might be impossible to produce the arrangement of apple trees that Gapeun described using this program.

Since Iha is now busy revising the program, it is up to you to determine whether the arrangement of apple trees that Gapeun described can be produced using the two watering cans.

Input

The first line gives the natural number $N$ . ( $1 \leq N \leq 100\ 000$ ) This is the number of apple trees Iha planted in the backyard.

The second line gives $N$ integers $h_1,h_2,\cdots,h_N$ separated by spaces. ( $0 \leq h_i \leq 10\ 000$ ) $h_i$ is the height Gapeun wants for the $i$ -th tree.

Output

On the first line, print “YES” if the watering cans can make every tree reach the height Gapeun wants, or “NO” otherwise, without the quotation marks.

Examples4

Example 1
Input
```
1
0
```
Expected output
```
YES
```
Example 2
Input
```
2
4 3
```
Expected output
```
NO
```
Example 3
Input
```
3
10000 1000 100
```
Expected output
```
YES
```
Example 4
Input
```
5
1 3 1 3 1
```
Expected output
```
NO
```