Minimum Total Time for Concurrent Tasks

You are given an array of integers representing the time required for each task. Two tasks can be executed concurrently, which means they can run in parallel. The objective is to determine the minimum total time needed to complete all tasks by optimally pairing them. If there is an odd number of tasks, one task will be executed alone.

The optimal strategy is to sort the task times in non‐increasing order and then pair the tasks sequentially. Formally, if the sorted task times are \(t_1 \ge t_2 \ge \dots \ge t_n\), then the minimum total time required is given by:

[ T_{min} = \max_{0 \le i < \lceil n/2 \rceil} t_{2i+1} ]

where tasks \(t_{2i+1}\) (using 1-indexing) represent the longer task in each pair. Print the computed minimum total time.

inputFormat

The first line of input contains a single integer \(n\) (\(1 \le n \le 10^5\)), representing the number of tasks. The second line contains \(n\) space-separated integers, each representing the execution time of a task.

outputFormat

Output a single integer representing the minimum total time required to complete all tasks when executed optimally, with at most two tasks running concurrently.

5
4 3 2 3 1

4