题目描述

农夫约翰有 $N$ 头奶牛正在过乱头发节。每一头牛都站在同一排面朝东方，而且每一头牛的身高为 $h_i$。第 $N$ 头牛在最前面，而第 $1$ 头牛在最后面。 对于第 $i$ 头牛前面的第 $j$ 头牛，如果 $h_i>h_{i+1}$ 并且 $h_i>h_{i+2} \cdots h_i>h_j$，那么认为第 $i$ 头牛可以看到第 $i+1$ 到第 $j$ 头牛。

定义 $C_i$ 为第 $i$ 头牛所能看到的别的牛的头发的数量。请帮助农夫约翰求出 $\sum_{i=1}^n C_i$。

输入格式

输入共 $N+1$ 行。

第 $1$ 行输入一个整数 $N$，表示奶牛的数量。

接下来 $N$ 行，每行一个整数 $h_i$，表示奶牛 $i$ 的高度。

输出格式

输出一个整数表示 $C_i$ 到 $C_n$ 的和。

样例输入输出

样例输入

6
10
3
7
4
12
2

样例输出

5

数据范围

对于 $100%$ 的数据，保证 $1 \le N \le 80,000$，$1 \le h_i \le 1,000,000,000$。

样例解释

        -
-       -
-   -   -
-   -   -
- - - - -
- - - - - -
1 2 3 4 5 6

牛面向右边 -->

对于第 $1$ 头牛来说，可以看到编号为 $2,3,4$ 的牛。

对于第 $2$ 头牛来说，不能看到任何牛的头发。

对于第 $3$ 头牛来说，可以看到编号为 $4$ 的牛。

对于第 $4$ 头牛来说，不能看到任何牛的头发。

对于第 $5$ 头牛来说，可以看到编号为 $6$ 的牛。

对于第 $6$ 头牛来说，不能看到任何牛的头发。

所以答案就是 $3+0+1+0+1+0=5$。