Description

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

Input

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

Output

For each S, a single line containing d, or a single line containing "no solution".

Sample Input

Sample Output

HINT

題意：給你一個數(shù)字集合，讓你從這個集合中找出四個數(shù)字，讓他們滿足a + b + c = d，并且d是滿足條件中的最大值。

解決方法：如果直接枚舉，O(n^4)肯定會超時。我們可以轉(zhuǎn)換一下a+b=d-c，我們先枚舉d-c，然后再用二分進(jìn)行求a+b。復(fù)雜度就變成了O(n^2logn)

#include<cstdio>#include<cstring>#include<algorithm>#define INF 536870919using namespace std;int a[1010];int main(){	int n;	while(~scanf("%d",&n)&&n)    {        for(int i=0;i<n;i++)            scanf("%d",&a[i]);        sort(a,a+n);//排序        int flag=0;        for(int i=n-1;i>=0;i--){            for(int j=n-1;j>=0;j--){                if(i==j)                    continue;                int cnt=a[i]-a[j];//求d-c                int l=0,r=j-1;                while(l<r)//二分求a+b                {                    if(a[l]+a[r]==cnt)                    {                        flag=1;                        PRintf("%d/n",a[i]);                        break;                    }                    else if(a[l]+a[r]<cnt)                        l++;                    else                        r--;                }                if(flag)                    break;            }            if(flag)                break;        }        if(!flag)            printf("no solution/n");    }	return 0;}