Pattern

Interview

Time limit1sMemory limit512 MB

Summary

Given a sequence of grid points, decide whether it is a valid Android unlock pattern under the no-repeat and no-skipped-point rules.

Level: Medium4 of 10
Topics: Implementation, Simulation, Array, Hash map
Solved: No attempts yet

Problem

Android has a way to unlock a phone that uses a pattern as the password. Number the 9 points of a 3×3 grid, choose some of them to form a sequence, and connect the points of adjacent numbers in the sequence in order; the path drawn this way is a pattern. The length of the pattern is the length of the sequence that represents it.

A pattern has the following restrictions.

The length of the pattern is at least 3.
No point appears more than once in the sequence that represents the pattern.
On the line segment connecting adjacent points of the sequence, there cannot be a point that has not yet appeared.

For example, the pattern [1, 2, 3, 6] is possible, but [1, 3, 6] is impossible because the line segment connecting 1 and 3 contains a point that has not yet appeared. [1, 9, 6, 5] is impossible because 5 appears later but had not appeared when 1-9 was drawn, [1, 5, 9, 6, 5] is impossible because a point appears more than once, and [1, 5, 9, 6, 4] is possible.

Given a sequence that represents a pattern, determine whether it is a possible pattern.

Input

The first line gives the length of the pattern, L.

The next line gives the sequence Ai (1 ≤ i ≤ L) that represents the pattern, over L values.

Output

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

Constraints

3 ≤ L ≤ 9
1 ≤ Ai ≤ 9

Examples5

Example 1
Input
```
4
1 2 3 6
```
Expected output
```
YES
```
Example 2
Input
```
3
1 3 6
```
Expected output
```
NO
```
Example 3
Input
```
4
1 9 6 5
```
Expected output
```
NO
```
Example 4
Input
```
5
1 5 9 6 5
```
Expected output
```
NO
```
Example 5
Input
```
5
1 5 9 6 4
```
Expected output
```
YES
```