Polygon

Interview

Time limit1sMemory limit128 MB

Summary

Decide whether N given segment lengths can form the sides of some convex polygon, which reduces to checking that the largest length is smaller than the sum of the rest.

Level: Easy3 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

You are given the lengths of $N$ segments. Determine whether all of these segments can be arranged, in some order, as the sides of a convex polygon.

In this problem a polygon is considered convex if every interior angle is strictly greater than $0$ degrees and strictly less than $180$ degrees; equivalently, no three consecutive vertices are collinear.

Input

The first line contains an integer $N$ , the number of sides of the polygon ( $3 \le N \le 1000$ ). Each of the following $N$ lines contains an integer $a_i$ , the length of one side ( $1 \le a_i \le 10000$ ).

Output

Print YES if a convex polygon can be built using every one of the $N$ segments exactly once, in any order, as its sides. Otherwise, print NO SOLUTION.

Hint

Examples4

Example 1
Input
```
4
7
4
5
4
```
Expected output
```
YES
```
Example 2
Input
```
3
3
4
5
```
Expected output
```
YES
```
Example 3
Input
```
3
1
2
3
```
Expected output
```
NO SOLUTION
```
Example 4
Input
```
3
1
1
5
```
Expected output
```
NO SOLUTION
```