BOI7SEQ - Sequence

no tags 

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
atharva_rockx: 2020-05-01 13:27:15

AC ez

nadstratosfer: 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
hello_world123: 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
neha1824: 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
leoamish300: 2018-02-10 08:12:30

Don't be a fool. The input is NOT sorted always.

bhabya_brj: 2018-01-24 06:17:20

@akshayvenkat where is it specifed?

code_aim: 2017-10-20 22:12:02

Nice one!!

akshayvenkat: 2016-07-05 18:07:41

the input seems to be sorted always

minhthai: 2016-03-17 16:16:04

O(n) in java cannot pass, just need 0.5s more :(((


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