B. Card Counting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The officers stop in Las Vegas, a city known for its magic shows and card games!

Equipped with a fresh deck of cards from the magic shop, the officers decide to play a game. They have a deck with a permutation of $$$n$$$ cards, numbered from $$$1$$$ to $$$n$$$. They will draw cards one at a time, and keep track of their score in the following way:

On the $$$i$$$-th draw, an officer will draw the card with number $$$c_i$$$. For every card in the (initially empty) discard pile, if the card's number is greater than $$$c_i$$$, that officer will add $$$c_i + k$$$ to their score, where $$$k$$$ is the value of the card. Finally, the officer adds card $$$c_i$$$ to the discard pile.

The officers will repeat this process until the deck is empty. Can you help them calculate what their final score will be?

Input

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of cards in the deck.

The next line contains $$$n$$$ integers $$$c_1,c_2\dots,c_n$$$ $$$(1 \leq c_i \leq n)$$$ — the cards of the deck in the order in which they were drawn.

Output

Output a single integer, the score the officers will end with.

Examples
Input
3
1 2 3
Output
0
Input
5
1 4 2 3 5
Output
13
Note

For the first test, the card with number 1 is drawn, then card 2, then card 3. No card in the discard pile is ever greater than a drawn card, so the score is 0.

For the second test, the officers increases their score by (4+2) when they draw the card numbered with a 2, and the officers increase their score by (3+4) when they draw the card numbered with a 3. Thus, their final score is 13.