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 accross 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
Description:
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.
 (here persons are denoted by there crossing time.)1,2,5,10 <>total= 17
hide comments
pandey101299:
20190325 10:12:07
thanks@pranjulpal18 

pranjulpal18:
20190102 18:34:52
See for n=4 to 8 on pen and paper and you will get the formula. 

pranjulpal18:
20190102 18:32:01
My 101th :)


:D:
20180921 23:43:45
Fun problem. 

julkas:
20180912 09:56:37
@shubham_001 Can you explain example test case, please?

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