BOI7SEQ  Sequence
We are given a sequence a1 , ..., an . We can manipulate this sequence using the operation reduce(i), which replaces elements ai and ai+1 with a single element max(ai , ai+1 ), resulting in a new shorter sequence. The cost of this operation is max(ai , ai+1 ). After n−1 operations reduce, we obtain a sequence of length 1. Our task is to compute the cost of the optimal reducing scheme, i.e. the sequence of reduce operations with minimal cost leading to a sequence of length 1.
Input
The first line contains n (1 ≤ n ≤ 1,000,000), the length of the sequence. The following n lines contain one integer ai , the elements of the sequence (0 ≤ ai ≤ 1,000,000,000).
Output
In the first and only line of the output print the minimal cost of reducing the sequence to a single element.
Example
Input:
3
1
2
3
Output: 5
hide comments
nadstratosfer:
20190328 08:25:58
Frustrating to crack, and in the end the stupid time limit makes this an input test: TLE in PyPy, 0.01s in CPP. 

hello_world123:
20180718 19:12:39
Good question !!!


neha1824:
20180707 21:00:15
I am getting correct output for all test cases at spojtoolkit.com yet my solution is not getting accepted Last edit: 20180707 21:02:30 

leoamish300:
20180210 08:12:30
Don't be a fool. The input is NOT sorted always. 

bhabya_brj:
20180124 06:17:20
@akshayvenkat where is it specifed? 

code_aim:
20171020 22:12:02
Nice one!! 

akshayvenkat:
20160705 18:07:41
the input seems to be sorted always 

minhthai:
20160317 16:16:04
O(n) in java cannot pass, just need 0.5s more :((( 
Added by:  Race with time 
Date:  20101104 
Time limit:  0.181s0.362s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Baltic Olympiad 2007 