#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

One Number Left - Repovive Starter Round 3 | Repovive

12C. One Number Left

1500 pts1s256 MB

You are given an array $a$ of length $n$ .

In one operation, you choose a position between two adjacent elements of the current array and split it into a non-empty prefix and a non-empty suffix. Then you choose one of these two parts and delete it.

The cost of the operation is equal to the maximum value among the deleted elements.

Your goal is to perform operations until exactly one element remains. Find the minimum possible total cost.

Constraints

$1 \le n \le 2 \times 10^5$
$0 \le a_i \le 10^9$

Input

n

a_1\quad a_2\quad \cdots\quad a_n

Output

\text{ans}

Here, $\text{ans}$ is the minimum possible total cost.

Samples

Input

1
42

Explanation

The array already contains exactly one element, so no operation is needed.

Output

Input

3
3 1 4

Explanation

One optimal way is to split the array into [3, 1] and [4], then delete [3, 1]. The cost is $3$ , and only the number $4$ remains.

Output

Input

5
5 0 100 0 4

Explanation

One optimal way uses three operations. First delete [5, 0] with cost $5$ . The remaining array is [100, 0, 4]. Then delete [4] with cost $4$ . Finally delete [0] with cost $0$ . The total cost is $9$ , and only $100$ remains.

Output

You are given an array $a$ of length $n$ .

The cost of the operation is equal to the maximum value among the deleted elements.

Your goal is to perform operations until exactly one element remains. Find the minimum possible total cost.

$1 \le n \le 2 \times 10^5$
$0 \le a_i \le 10^9$

n

a_1\quad a_2\quad \cdots\quad a_n

\text{ans}

Here, $\text{ans}$ is the minimum possible total cost.

One optimal way is to split the array into [3, 1] and [4], then delete [3, 1]. The cost is $3$ , and only the number $4$ remains.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

12C. One Number Left

Constraints

Input

Output

Samples

12C. One Number Left

Constraints

Input

Output

Samples