Description

Ante and Goran are preparing $n$ teams. Each of them has one algorithm that needs to be explained to all teams.

Of course, they cannot both explain to the same team at the same time, and neither of them can explain to multiple teams at the same time.

Given the time needed to explain to each team, determine the minimum total time required.

Input Format

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

The next line contains $n$ space-separated integers $a_i$, where $a_i$ is the time needed to explain to team $i$.

Output Format

Output a single line: the minimum total time required.

3
2 2 2

6

3
4 1 2

8

4
1 3 2 1

7

Hint

Explanation for Sample 1

Each team needs $2$ units of time to understand and implement an algorithm. The following is one feasible teaching plan.

Explanation for Sample 2

One optimal schedule is that Ante teaches teams $2, 3, {\color{red}x}, 1$ in order, but there is a $1$ unit time pause at $\color{red}x$. Goran will teach teams $1, 3, 2$ in order.

Constraints

• For $40\%$ of the testdata, $1 \le n \le 7$.
• For $100\%$ of the testdata, $1 \le n \le 3 \times 10^5$.

For all valid $a_i$, $a_i \in [1, 3 \times 10^5]$.

Notes

This problem is translated from COCI2014-2015 CONTEST #4 T3 PRIPREME.

Translated by ChatGPT 5