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

Added by:Race with time
Date:2010-11-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Baltic Olympiad 2007

hide comments
2020-05-01 13:27:15
AC ez
2019-03-28 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.

Edit: As of May'2020 the corrected TL now allows AC even in pure Python.

Last edit: 2020-05-28 11:22:21
2018-07-18 19:12:39
Good question !!!
Done in O(1) space and O(n) time .
Think greedily

Last edit: 2018-07-18 19:30:32
2018-07-07 21:00:15
I am getting correct output for all test cases at spojtoolkit.com yet my solution is not getting accepted

Last edit: 2018-07-07 21:02:30
2018-02-10 08:12:30
Don't be a fool. The input is NOT sorted always.
2018-01-24 06:17:20
@akshayvenkat where is it specifed?
2017-10-20 22:12:02
Nice one!!
2016-07-05 18:07:41
the input seems to be sorted always
2016-03-17 16:16:04 minhthai
O(n) in java cannot pass, just need 0.5s more :(((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.