Rooftop Garden

Source: Baekjoon Online Judge

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ buildings arranged from left to right. The owner of building $i$ can see the rooftops of consecutive buildings to the right until the first building whose height is greater than or equal to building $i$. Compute the total number of rooftops visible to all owners.

Input

The first line contains $N$. Each of the next $N$ lines contains one building height, in left-to-right order.

Output

Print one integer: the total number of visible owner-rooftop pairs described above.

Subtasks

• Subtask 1 (30 points): $N\le2000$; all other conditions are unchanged.
• Subtask 2 (70 points): $1\le N\le80000$, $1\le H_i\le10^9$.

Examples

Input

6
10
3
7
4
12
2

Output

5

Explanation

Consider the buildings from left to right:

• Height $10$ sees the rooftops of heights $3,7,4$. Height $12$ is the first building with height at least $10$, so the view stops before it: contribution $3$.
• Height $3$ immediately meets height $7\ge3$, so it sees no rooftop: contribution $0$.
• Height $7$ sees height $4$, then height $12\ge7$ blocks the view: contribution $1$.
• Height $4$ is immediately blocked by height $12\ge4$: contribution $0$.
• Height $12$ sees the final rooftop of height $2$: contribution $1$.
• The last building has nothing to its right: contribution $0$.

The total is $3+0+1+0+1+0=5$, so the output is 5.