SHINCARD - Shinchan and Magic Card

An alien group has attacked Kasukabe so whole city is in big trouble! All people (count is N) in Kasukabe try to run away so is Shinchan! They came across a bridge over a river, and that bridge has been cursed by aliens. Bridge will collapse when someone passes over it.

Shinchan as a legend calls an ultra legend Buri Buri Zaemon by his magic card. Buri Buri appears and suggests Shinchan that whenever a person having magic card in his hand passes over the bridge then it will not collapse but since bridge is fragile only maximum 2 persons at a time can pass over it (and one of them should have magic card in his hand). All citizens of Kasukabe have to go to other side of the river using bridge as quickly as possible. When two persons A and B pass over bridge, it takes MAX(time(A), time(B)) to get them on the other side of river (where time(i) is the time taken by ith person to pass over the bridge). Shinchan has an array of all time[] values of all citizens.

Find the minimum time in which they escape the bridge. (There is only one magic card)

Input

First line contains N, 1 <= N <= 100000.

Next line contains N integers, 1 <= time[i] <= 1000000000 for each 1 <= i <= N.

Output

Output the minimum time to get all persons over the other side of the river.

Example

Input:
4
1 2 5 10

Output:
17

Explanation

  • 1 and 2 cross,
  • 1 comes back,
  • 5 and 10 cross,
  • 2 comes back,
  • 1 and 2 cross.

Total = 2 + 1 + 10 + 2 + 2 = 17.


Added by:MichaelJ
Date:2018-09-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own

hide comments
2019-12-23 10:15:46
Testcases not strong enough, doesn't consider cases in which the second person is slow
such as
4
1 1000 1000 1000

Last edit: 2019-12-23 10:16:19
2019-12-23 07:42:24
my 50th with such special one
2019-03-25 10:12:07
thanks@pranjulpal18
2019-01-02 18:34:52
See for n=4 to 8 on pen and paper and you will get the formula.
2019-01-02 18:32:01
My 101th :)
AC at one go!!!!!
Thanks @jareehd
2018-09-21 23:43:45 :D
Fun problem.
2018-09-12 09:56:37
@shubham_001 Can you explain example test case, please?
>>Reply : Description Added!

Last edit: 2018-09-12 14:24:45
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.