문제

Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing. The game starts with a sequence of $N$ positive integers $a_1,a_2,\ldots,a_N$ ($2\le N\le 262,144$), each in the range $1\ldots 10^6$. In one move, Bessie can take two adjacent numbers and replace them with a single number equal to one greater than the maximum of the two (e.g., she might replace an adjacent pair $(5,7)$ with an $8$). The game ends after $N-1$ moves, at which point only a single number remains. The goal is to minimize this final number.

Bessie knows that this game is too easy for you. So your job is not just to play the game optimally on $a$, but for every contiguous subsequence of $a$.

Output the sum of the minimum possible final numbers over all $\frac{N(N+1)}{2}$ contiguous subsequences of $a$.

입력

First line contains $N$.

The next line contains $N$ space-separated integers denoting the input sequence.

출력

A single line containing the sum.

예제 입력 1

6
1 3 1 2 1 10

예제 출력 1

115

점수

Test cases 2-3 satisfy $N\le 300$.Test cases 4-5 satisfy $N\le 3000$.In test cases 6-8, all values are at most $40$.In test cases 9-11, the input sequence is non-decreasing.Test cases 12-23 satisfy no additional constraints.