H. Sort Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$a$$$ of length $$$n$$$. You can perform the following operation:

  • Choose a segment $$$1\leq l\leq r\leq n$$$ and sort it. The cost of such operation is $$$a_l + \dots + a_r$$$.

Your task is to sort the permutation with minimal total cost.

Input

The first contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the length of the permutation $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — elements of permutation $$$a$$$.

Output

Output the minimal total cost.

Examples
Input
6
3 1 2 4 6 5
Output
17
Input
4
1 4 3 2
Output
9
Note

In the first sample, you can perform the following operations:

  1. $$$[\color{orange}3, \color{orange}1, \color{orange}2, 4, 6, 5] \rightarrow [\color{orange}1, \color{orange}2, \color{orange}3, 4, 6, 5]$$$, the cost is $$$1+2+3=6$$$.
  2. $$$[1, 2, 3, 4, \color{orange}6, \color{orange}5] \rightarrow [1, 2, 3, 4, \color{orange}5, \color{orange}6]$$$, the cost is $$$5+6=11$$$.
The total cost is $$$6+11=17$$$.