P2866 [USACO06NOV] Bad Hair Day S

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$.

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 a single line with one integer, the value of $C_1 + C_2 + \cdots + C_N$.

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