/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はプログラミングコンテストのチーム戦に向けて、メンバーの中から異なる 2 人を選んでペアを 1 組作ることにしました。
チームには N 人のメンバーがおり、i 番目（1 \leq i \leq N）のメンバーはプログラミング能力を表す正の整数値 A_i を持っています。なお、異なるメンバーが同じ能力値を持つこともありますが、別人であれば区別してペアに選ぶことができます。
i 番目のメンバーと j 番目のメンバー（1 \leq i < j \leq N）からなるペアの「総合力」は、その 2 人の能力値の和 A_i + A_j として定義されます。
高橋君は、総合力が最大となるようにペアを選びたいと考えています。
ペアの総合力としてあり得る最大値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N A_1 A_2 \ldots A_N
- 1 行目には、メンバーの人数を表す整数 N が与えられる。
- 2 行目には、各メンバーの能力値を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
ペアの総合力としてあり得る最大値を 1 行で出力せよ。
入力例 1
5 3 1 4 1 5
出力例 1
9
入力例 2
3 100 200 150
出力例 2
350
入力例 3
10 500000000 1000000000 250000000 750000000 100000000 999999999 300000000 600000000 400000000 800000000
出力例 3
1999999999
Score : 300 pts
Problem Statement
Takahashi is preparing for a team programming contest and has decided to select 2 different people from the members to form one pair.
The team has N members, and the i-th member (1 \leq i \leq N) has a positive integer value A_i representing their programming ability. Note that different members may have the same ability value, but as long as they are different people, they can be distinguished and selected for a pair.
The "combined strength" of a pair consisting of the i-th member and the j-th member (1 \leq i < j \leq N) is defined as the sum of their ability values, A_i + A_j.
Takahashi wants to select a pair that maximizes the combined strength.
Find the maximum possible value of the pair's combined strength.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of members.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the ability values of each member.
Output
Print the maximum possible value of the pair's combined strength on one line.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
9
Sample Input 2
3 100 200 150
Sample Output 2
350
Sample Input 3
10 500000000 1000000000 250000000 750000000 100000000 999999999 300000000 600000000 400000000 800000000
Sample Output 3
1999999999