Apteka

Jaś is standing at the very back of the queue in front of a pharmacy. Because Jaś is in a great hurry, he decides to try swapping places with some of the people ahead of him, even if he has to pay for it.

Every person is willing to swap, but the $i$-th person must be paid $c_i$ for each single place they move further back in the queue. More precisely, if Jaś is $k$ places ($k > 0$) further from the cashier than some person and wants to swap places with them, he must pay that person $k \cdot c_i$.

Jaś would like to be first in the queue. Determine how to make the swaps so that he spends as little as possible.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of people standing in front of Jaś in the pharmacy queue.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$), where $c_i$ is the amount Jaś must pay the $i$-th person to move them one place further back in the queue. The people are numbered starting from the one Jaś directly stands behind, that is, from the back of the queue toward its front.

Print a single integer: the minimum amount Jaś must pay to become first in the queue.

In the example, Jaś first swaps with the third person from the front for a cost of $2 \cdot 2$, and then with the person at the front for a cost of $3 \cdot 2$. The total cost is therefore $10$.