Minimize Maximum Pair Sum In Array

medium
The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.
Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.
Return the minimized maximum pair sum after optimally pairing up the elements.

Input Format

Input and output are managed for you. Just complete the function.

Output Format

Input and output are managed for you. Just complete the function.

Constraints

n == nums.length
2 <= n <= 105
n is even.
1 <= nums[i] <= 105

Notice

NA

Example

Input
4
3 5 2 3
Output
7
Previous
Maximum Absolute Sum Of Any Subarray
Next
Remove All Adjacent Duplicates In String

Related Questions