You are given an array A of N integers (N is even). Split array A into N/2 pairs in such a way that the largest sum of any pair will be as small as possible. Each element has to belong to exactly one pair.

For example, given array A = [4, 5, 3, 1], we can split it into pairs in three ways:

(4, 5) and (1, 3), where the sums of the pairs' elements are 9 and 4. The largest sum is 9.

(4, 1) and (5, 3), where the sums of the pairs' elements are 5 and 8. The largest sum is 8.

(4, 3) and (5, 1), where the sums of the pairs' elements are 7 and 6. The largest sum is 7.

In the above splits, pairs with the largest sums of elements are (4, 5), (5, 3) and (4, 3). Of these, the smallest is 4 + 3 = 7.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A of N integers, returns the largest sum of the pairs' elements in the optimal split.

Examples:

1. Given A = [4, 5, 3, 1], the function should return 7, as explained above.

2. Given A = [2, 3, 1, 1], the function should return 4. The optimal split is (1, 3) and (1, 2), where the sums of pairs are 1 + 3 = 4 and 1 + 2 = 3, and 4 is the larger.

3. Given A = [−5, −6], the function should return −11. We can make only one pair, (−5, −6), whose sum is −11.

4. Given A = [2, 2, 2, 2, 2, 2], the function should return 4. The only possible split is (2, 2), (2, 2) and (2, 2), where the sums of all pairs are equal to 4.

Write an efficient algorithm for the following assumptions:

N is an even integer within the range [2..100,000];

each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

#include
#include

using namespace std;

int solution(vector A){
cerr << "Tip: Use cerr to write debug messages on the output tab.";
return 0;