Preparation Lectures

Ante and Goran are coaching $N$ teams of students for a programming competition. Each of the two has one algorithm to explain, so every team has to attend one lecture by Ante and one lecture by Goran.

Team $i$ needs $t_i$ units of time to understand and implement an algorithm, and that time is the same for both lectures. A lecture runs without interruption. Ante and Goran cannot lecture the same team at the same moment, and neither of them can lecture two teams at the same moment. Either lecturer is allowed to stay idle at any moment, and a team may attend the two lectures in either order.

Find the smallest amount of time in which both lecturers finish all of their lectures.

The first line contains the integer $N$, the number of teams.

The second line contains $N$ integers $t_1, t_2, \dots, t_N$ separated by spaces, where $t_i$ is the time team $i$ needs to understand and implement an algorithm.

Every number in the input lies in the interval $[1, 3 \times 10^5]$.

Print the smallest amount of time as a single integer.

In the first example every team spends 2 units of time. Ante can lecture team 1, then team 2, then team 3, while Goran lectures team 3, then team 1, then team 2.

In the second example Ante can lecture team 2 and team 3 in that order, stay idle for 1 unit of time, and then lecture team 1, while Goran lectures team 1, then team 3, then team 2.