Iha 最近购买了苹果树种子，并将它们排成一列种在农场后院，编号从 1 到 $N$。这些树的初始高度均为 0。

为了让苹果树茁壮成长，Iha 准备了两个喷壶。一个喷壶可以将一棵树的高度增加 1，另一个喷壶可以将一棵树的高度增加 2。这两个喷壶必须同时使用，且不能将喷壶用于没有树的土壤。也可以将两个喷壶同时用于同一棵树，使其高度增加 3。

Iha 已经完成了喷壶管理系统的编程，正准备开始培育苹果树。就在这时，Galmja 来访并表示，希望每棵苹果树的高度能达到某种特定的布局。Iha 开始有些担心，因为他可能无法通过程序实现 Galmja 所要求的苹果树布局。

由于 Iha 现在忙于修改程序，判断是否能利用这两个喷壶实现 Galmja 所要求的苹果树布局的任务就交给你了。

输入格式

第一行给出一个自然数 $N$ ($1 \le N \le 100\,000$)，表示 Iha 在后院种植的苹果树数量。 第二行给出 $N$ 个整数 $h_1, h_2, \dots, h_N$，以空格分隔 ($0 \le h_i \le 10\,000$)。 其中 $h_i$ 表示 Galmja 希望第 $i$ 棵树达到的高度。

输出格式

如果可以通过喷壶使所有树的高度达到 Galmja 希望的高度，则输出 “YES”，否则输出 “NO”（不含引号）。

样例

输入 1

1
0

输出 1

YES

输入 2

2
4 3

输出 2

NO

输入 3

3
10000 1000 100

输出 3

YES

输入 4

5
1 3 1 3 1

输出 4

NO