안드로이드 잠금화면을 풀기 위한 방법 중 3x3의 9개의 점을 연결해 패턴을 암호로 사용하는 방법이 있다. 각 점에 번호를 매겨 하나의 수열로 나타냈을 때, 수열에서 인접한 번호의 점을 순서대로 연결해 그려지는 경로를 패턴이라 하자. 이 때 패턴의 길이는 패턴을 나타내는 수열의 길이이다.

패턴에는 다음과 같은 제약이 있다.

• 패턴의 길이는 3 이상 이다.
• 패턴에 같은 점은 최대 한번 등장한다.
• 점과 점 사이의 선분에는 아직 등장하지 않은 점이 있을 수 없다.

안드로이드 패턴이 입력되었을 때, 유효한 패턴인지 알고싶다.

Input

첫 번째 줄에 패턴의 길이 $L$을 입력받는다. ($3 \le L \le 9$)

다음 줄에 $L$ 개의 정수 $a_1, \cdots, a_L$ 를 입력받는다. 이는 패턴이 $a_1, \ldots, a_L$ 번 점을 순서대로 지난다는 뜻이다. ($1 \le a_i \le 9$)

Output

유효한 패턴이라면 "YES", 그렇지 않다면 "NO" 를 출력한다.

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