Ante and Goran's Lecture Scheduling

Ante and Goran are preparing to deliver lectures to n teams. Each of them has an algorithm that they need to explain to every team. However, they cannot lecture the same team at the same time, and each lecturer cannot handle more than one team at the same time.

For each team, you are given the time required to deliver a lecture. Note that the time given is the same for both lecturers.

Since each team needs to hear both lectures (one from Ante and one from Goran) and the lectures for a single team cannot be conducted concurrently, the minimum total time required is given by the formula:

$$ T_{min} = \max\left( \sum_{i=1}^{n} t_i,\, 2\max_{1 \le i \le n} t_i \right) $$

Your task is to compute the minimum time needed to finish all lectures.

inputFormat

The input consists of two lines:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of teams.
• The second line contains n space-separated integers t₁, t₂, ... , t_n (1 ≤ t_i ≤ 10⁹), where t_i denotes the time required for a lecture for the i-th team.

outputFormat

Output a single integer denoting the minimum time required to complete all lectures.

sample

3
2 2 2

6