Bridge Crossing Problem

You are given a group of travelers who need to cross a bridge at night. They have only one torch, and the light of the torch can allow at most two travelers to cross at a time. Moreover, a crossing can only happen if one or two travelers carry the torch; no crossing is allowed without the torch or with more than two travelers simultaneously.

Each traveler takes a specific amount of time to cross the bridge. When two travelers cross together, they move at the pace of the slower one. The goal is to determine the minimum total time required for all travelers to cross the bridge.

Input Format: The first line contains an integer n, representing the number of travelers. The second line contains n space-separated integers, where each integer denotes the time required by a traveler to cross the bridge.

Output Format: Output a single integer representing the minimum total time required for all travelers to cross the bridge.

Note: It is assumed that the travelers strategize optimally to minimize the total crossing time.

inputFormat

The input consists of two lines:

• The first line contains an integer n (n ≥ 1), indicating the number of travelers.
• The second line contains n space-separated positive integers. Each integer represents the time needed for a traveler to cross the bridge.

outputFormat

Output a single integer – the minimum total time required for all travelers to cross the bridge.

sample

1
3

3