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
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.
|
|
hello_world123:
2018-07-18 19:12:39
Good question !!!
|
|
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 |