题目描述

农夫 John 的 $N\ (1 ≤ N ≤ 80,000)$ 只奶牛中，有一些也许正在经历发型糟糕的一天。每只奶牛对自己乱糟糟的发型都有自知之明，农夫 John 想知道所有奶牛能看到其他奶牛头顶的数量之和。

任意奶牛 $i$ 身高记为 $h_i\ (1 ≤ h_i ≤ 10^9)$，所有奶牛面向东方（本题示意图的右面）依次站成一条线。因此，奶牛 $i$ 能够看到在它前面的（奶牛 $i+1$，$i+2$…）所有身高比它低的奶牛，直到被一头比它高的奶牛挡住。

考虑如下的例子：

        =
=       =
=   -   =         Cows facing right ->
=   =   =
= - = = =
= = = = = =
1 2 3 4 5 6 

• 奶牛 $1$ 可以看见奶牛 $2, 3, 4$ 的头顶；
• 奶牛 $2$ 无法看到任何奶牛的头顶；
• 奶牛 $3$ 可以看见奶牛 $4$ 的头顶；
• 奶牛 $4$ 无法看到任何奶牛的头顶；
• 奶牛 $5$ 可以看见奶牛 $6$ 的头顶；
• 奶牛 $6$ 无法看到任何奶牛的头顶。

用 $c_i$ 表示奶牛 $i$ 能够看到头顶的奶牛个数；请计算 $c_1$ 至 $c_N$ 的和。对于上面这个例子，其和为：$3 + 0 + 1 + 0 + 1 + 0 = 5$。

输入格式

第 $1$ 行：奶牛数 $N$；

第 $2$ 行至 $N+1$ 行：第 $i+1$ 行包含一个整数，表示奶牛 $i$ 的高度。

输出格式

第 $1$ 行：$c_1$ 至 $c_N$ 的累加和。

6
10
3
7
4
12
2

5