Cake Appearance

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

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?


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

9 1 9 6 5 3

Sample Output 1


Sample Input 2

1 2 3

Sample Output 2


Explanation for Sample Output 2

Rearrange the cakes to be 2 3 1.

Sample Input 3

104 70 98 83 88

Sample Output 3



There are no comments at the moment.