Trouble happened — Sergei's spy has been uncovered, and now he needs to run away urgently! But before escaping, he must delete all incriminating data from his computer.
There are N files saved on Sergey's computer, numbered from 1 to N. Each of the files has a size in bytes: a
1, a
2, . . . , a
N. All data on Sergey's computer is well encrypted. The spy determined that it would take at least a
i−1 and a
i+1 seconds to delete file number i (it would take a
2< /sub> seconds, and to remove the last — aN−1 seconds). When only one file remains, it is deleted instantly. After deleting the file with the number i, the rest of the files are renumbered sequentially.
Sergey has very little time left, and he still needs to pack his things, so he asks for your help. Determine the minimum time it takes for the spy to delete all files.
Sergey can delete files sequentially in any order.
Input
The first line of the output contains a single integer N (1 ≤ N ≤ 105) — the number of files on the spy's computer.
Each of the next N lines contains one integer ai (1 ≤ ai ≤ 104) — size of the i file on Sergey's computer.
Imprint
In a single line print a single number — the minimum time that Sergey will need to delete all files.
Examples
| # |
Input |
Output |
| 1 |
5
1
2
3
1
100
| 4 |
| 2 |
1
1 |
0 |
Remark
In the first example, Sergey has files with sizes 1, 2, 3, 1, 100. One solution is shown below:
1. Delete the last file. This will take one second.
2. Then delete the size 2 file in one second.
3. Next, delete a file of size 3 in one second.
4. Now let's delete any of the remaining two files in one second.
5. The last file will be deleted instantly.
In total, Sergey will need 1 + 1 + 1 + 1 = 4 seconds.
In the second example, Sergey initially has only one file, which will be deleted immediately.