Iha recently bought apple tree seeds and planted them in a row in his backyard, numbered from $1$ to $N$. The initial height of all these trees is $0$.

To help the apple trees grow, Iha prepared two watering cans. One watering can increases the height of a tree by $1$, and the other increases the height of a tree by $2$. These two watering cans must be used simultaneously, and they cannot be used on soil where there is no tree. It is also possible to use both watering cans on the same tree to increase its height by $3$.

After programming the entire watering can management system, Iha was about to start growing the apple trees. At that moment, Galmja came over and said that he would like the heights of the apple trees to be in a specific configuration. Iha started to worry because it might not be possible to create the configuration Galmja suggested using his program.

Since Iha is busy modifying his program, it is now your task to determine whether the apple tree configuration suggested by Galmja can be achieved using the two watering cans.

Input

The first line contains a natural number $N$ ($1 \le N \le 100\,000$), which represents the number of apple trees Iha planted in his backyard.

The second line contains $N$ integers $h_1, h_2, \dots, h_N$ separated by spaces ($0 \le h_i \le 10\,000$), where $h_i$ is the height of the $i$-th tree that Galmja desires.

Output

If it is possible to make all trees reach the heights desired by Galmja using the watering cans, print "YES"; otherwise, print "NO" (excluding the quotation marks).

Examples

Input 1

1
0

Output 1

YES

Input 2

2
4 3

Output 2

NO

Input 3

3
10000 1000 100

Output 3

YES

Input 4

5
1 3 1 3 1

Output 4

NO