Minimizing the Best

Problem Statement

Minimizing the Best Problem Description Yash is studying the goals his football team scored across a series of matches. He must split all of the matches into pairs — every match belongs to exactly one pair — and each pair has a combined score , the sum of the goals of its two matches. The quality of a pairing is judged by its worst pair: the largest combined score it produces. Yash wants the pairing whose largest combined score is as small as possible. Given the goals scored in each match, return that minimum possible value of the largest combined score. Input Format The first line contains an integer N , the number of matches the team played. Each of the next N lines contains one integer, the number of goals scored in that match. Output Format Print a single integer: the smallest value that the largest pair sum can take over all ways of splitting the N matches into N / 2 pairs. Examples Example 1 Input 4 3 2 5 3 Output 7 Explanation The goals are [3, 2, 5, 3] . Pairing 2 with 5 and 3