One way to unlock an Android lock screen is to use a pattern as a password by connecting 9 dots arranged in a 3x3 grid. When each dot is numbered, the pattern can be represented as a sequence, where the path is drawn by connecting adjacent dots in the sequence in order. The length of the pattern is the length of the sequence representing it.

Patterns have the following constraints:

• The length of the pattern is at least 3.
• Each dot appears at most once in the pattern.
• A line segment between two dots cannot pass through a dot that has not yet appeared in the pattern.

Given an Android pattern, determine whether it is a valid pattern.

Input

The first line contains the length of the pattern $L$ ($3 \le L \le 9$).

The next line contains $L$ integers $a_1, \dots, a_L$, which means the pattern passes through dots $a_1, \dots, a_L$ in order ($1 \le a_i \le 9$).

Output

Print "YES" if the pattern is valid, and "NO" otherwise.

Examples

Input 1

8
9 2 7 6 1 8 3 4

Output 1

YES

Input 2

4
5 8 7 9

Output 2

YES

Input 3

4
2 8 7 9

Output 3

NO