Gym 100971C 水&愚&三角形

Description

standard input/output
Announcement

Statements

There is a set of n segments with the lengths l_i. Find a segment with an integer length so that it could form a non-degenerate triangle with any two segments from the set, or tell that such segment doesn't exist.

Input

The first line contains a single integer n(2 ≤ n ≤ 200000) — the number of segments in the set.

The second line contains n integers l_i separated by spaces (1 ≤ l_i ≤ 10⁹) — the lengths of the segments in the set.

Output

If the required segment exists, in the first line output «YES» (without quotes). In this case in the second line output a single integer x — the length of the needed segment. If there are many such segments, output any of them.

If the required segment doesn't exist, output «NO» (without quotes).

Sample Input

Input

2
3 4

Output

YES
2

Input

3
3 4 8

Output

YES
6

Input

3
3 4 9

Output

NO

 
题意：给你一些边 判断是否存在一条边 使得和其中的任意两条边组合都能形成三角形 

题解：将边排序之后 所要添加的边存在上下界
     ans1=a[n-1]-a[0];      
     ans2=a[0]+a[1];
     范围内 任意输出



 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int a[200005];
 5 int ans1,ans2;
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for(int i=0;i<n;i++)
10         scanf("%d",&a[i]);
11     sort(a,a+n);
12     ans1=a[n-1]-a[0];
13     ans2=a[0]+a[1];
14     if(ans1+1<ans2)
15     {
16         cout<<"YES"<<endl;
17         cout<<ans1+1<<endl;
18     }
19     else
20         cout<<"NO"<<endl;
21     return 0;
22 }