Alice runs a cake store. She has ~N~ cakes ready to be displayed on a line. Each cake has a value of ~a_i~.

Alice can arrange her ~N~ cakes in any order. However, she thinks that if the sum of two adjacent cakes in an arrangement is divisible by ~3~, the arrangement is considered ugly by her standards.

Is Alice able to display an arrangement that is not ugly?

Constraints

~1 \le N \le 10^6~

~1 \le a_i \le 10^9~

Subtask 1 [20%]

~1 \le N \le 10~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line of input will contain the integer ~N~.

The next line will contain ~N~ integers ~a_i~.

Output Specification

Output YES if Alice is able to display an arrangement that is not ugly, and NO otherwise.

Sample Input 1

6
9 1 9 6 5 3

Sample Output 1

NO

Sample Input 2

3
1 2 3

Sample Output 2

YES

Explanation for Sample Output 2

Rearrange the cakes to be 2 3 1.

Sample Input 3

5
104 70 98 83 88

Sample Output 3

NO