Sum Set

Time limit1sMemory limit128 MB

Summary

Given a set of distinct integers, find the largest element d that equals the sum of three other distinct elements.

Level: Medium6 of 10
Topics: Hash map, Brute force, Sorting
Solved: No attempts yet

Statement

You are given a set $S$ of integers. Among four distinct elements $a$ , $b$ , $c$ , $d$ of $S$ , find the largest $d$ such that $a + b + c = d$ .

Input

The input consists of several test cases.

The first line of each test case contains the size $n$ ( $1 \le n \le 1000$ ) of the set $S$ . Each of the next $n$ lines contains one element of $S$ , an integer between $-536870912$ and $536870911$ . The elements of a set are all distinct.

The last line of the input contains $0$ , marking the end of input.

Output

For each test case, print the largest $d$ that satisfies the condition on its own line. If no such $d$ exists, print no solution.

Examples4

Example 1

Input

Expected output

12
no solution

Example 2
Input
```
4
1
2
3
6
0
```
Expected output
```
6
```
Example 3
Input
```
5
2
3
5
7
12
0
```
Expected output
```
12
```

Example 4

Input

Expected output

6
no solution
8