Dividing Candy

Interview

Time limit1sMemory limit1024 MB

Summary

Given N boxes whose candy counts are powers of 2, decide whether the boxes can be split into two nonempty groups whose sums are both powers of 2.

Level: Medium6 of 10
Topics: Math, Greedy, Sorting, Bit manipulation
Solved: No attempts yet

Problem

Bob and Charlie are two brothers who like powers of 2 a lot. Their mum decided to give them N boxes of candy, each of them containing a number of candy bars that is a power of 2.

They want to split the boxes between them, that is, for each box, they will decide who gets it. Each box must be given to exactly one brother.

Now they wonder: is it possible that, for each of the two brothers, the total amount of candy bars he receives is also a power of 2?

For example, if N = 4 and the boxes contain 4, 4, 32, and 8 candy bars, the answer would be yes, as one possible solution is giving the third box to Bob (32 candy bars), and the remaining boxes to Charlie (4 + 4 + 8 = 16 candy bars in total).

Input

The first line contains an integer N (1 ≤ N ≤ 105), the number of boxes the brothers want to split. The second line contains N integers A1, A2, . . . , AN (0 ≤ Ai ≤ 105 for i = 1, 2, . . . , N), indicating that the i-th box has 2Ai candy bars.

Output

Output a single line with the uppercase letter “Y” if it is possible to split the boxes so that the total amount of candy received by each brother is a power of 2, and the uppercase letter “N” otherwise.

Examples4

Example 1
Input
```
4
2 2 5 3
```
Expected output
```
Y
```
Example 2
Input
```
1
42
```
Expected output
```
N
```
Example 3
Input
```
5
3 1 4 1 5
```
Expected output
```
N
```
Example 4
Input
```
7
0 0 1 2 3 4 5
```
Expected output
```
Y
```