Problem Description

Farmer John has $N$ cows on a Bad Hair Day.

All cows stand in a single line facing right, and they are numbered from left to right as $1, 2, \cdots, N$. Cow $N$ is at the front, and cow $1$ is at the back. The height of cow $i$ is $h_i$.

For the cows in front of cow $i$, if $h_i > h_{i+1}, h_i > h_{i+2}, \cdots, h_i > h_j$, then cow $i$ is considered able to see cows $i+1$ through $j$.

Define $C_i$ as the number of cows visible to cow $i$. Please help Farmer John compute $C_1 + C_2 + \cdots + C_N$.

Input Format

The input contains $N + 1$ lines.

The first line contains an integer $N$, the number of cows.
The next $N$ lines each contain an integer $h_i$, representing the heights of cows $1, 2, \cdots, N$.

Output Format

Output a single line with one integer, the value of $C_1 + C_2 + \cdots + C_N$.

6
10
3
7
4
12
2

5

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \leq N \leq 8 \times 10^4$, $1 \leq h_i \leq 10^9$.

Translated by ChatGPT 5