Building a Field

Interview

Time limit2sMemory limit512 MB

Summary

Given N points on a circle with arc lengths between consecutive points, decide whether four trees are the vertices of some rectangle.

Level: Medium5 of 10
Topics: Hash map, Geometry, Math, Implementation
Solved: No attempts yet

Problem

John is a meticulous person. On his farm he built a circular field with some trees planted right on the circumference of the field. Figure (a) below shows the field with the trees.

Now John wants to use a long rope and four of the field trees to demarcate a rectangle using the trees as vertices and the rope as edges. Figure (b) below shows two rectangles that can be demarcated using the trees of the field in figure (a).

Given the description of the positions of the trees in John's circular field, you must determine whether it is possible to demarcate a rectangle using four of the trees as vertices and the rope as edges.

Input

The first line contains an integer N (4 ≤ N ≤ 105) indicating the number of trees in the field. Trees are represented as points on a circumference. The second line contains N integers L1, L2, . . . , LN (1 ≤ Li ≤ 106 for i = 1, 2, . . . , N) indicating the arc lengths between each pair of consecutive trees. The arcs are given in counter-clockwise order. The total length of the circumference does not exceed 109.

Output

Output a single line with the uppercase letter “Y” if it is possible to demarcate a rectangle using the given trees, and the uppercase letter “N” otherwise.

Examples3

Example 1
Input
```
8
3 3 4 2 6 2 2 2
```
Expected output
```
Y
```
Example 2
Input
```
4
14 16 15 15
```
Expected output
```
N
```
Example 3
Input
```
6
3 7 7 3 10 10
```
Expected output
```
Y
```