Minimal Total Completion Time

Given an integer n representing the number of tasks and a list of n integers representing the duration of each task (in the given order), compute the minimal total time required to complete all tasks if you are allowed to perform up to two tasks simultaneously.

You must process the tasks in order. You can perform two tasks concurrently by pairing consecutive tasks; the time taken for a pair is the maximum of the two tasks' durations. If there is an odd number of tasks, the last task is processed individually.

Formally, if the tasks are given as \(t_1,t_2,\ldots,t_n\), the minimal total time \(T\) is computed as:

\[ T = \sum_{i=1}^{\lfloor n/2 \rfloor} \max\{t_{2i-1},t_{2i}\} + \begin{cases} t_n &\text{if } n \text{ is odd}\\ 0 &\text{otherwise} \end{cases} \]

inputFormat

The first line contains an integer (n) representing the number of tasks. The second line contains (n) space-separated integers denoting the durations of the tasks (in the given order).

outputFormat

Output a single integer: the minimal total time required to complete all tasks.## sample

3
4 2 5

9