OpenJudge

1:发型糟糕的一天

总时间限制:
2000ms
单个测试点时间限制:
1000ms
内存限制:
65536kB
描述

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

任意奶牛i身高记为 hi (1 ≤ hi ≤ 1,000,000,000),所有奶牛面向东方(本题示意图的右面)依次站成一条线。因此,奶牛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无法看到任何奶牛的头顶!

用ci表示奶牛i能够看到头顶的奶牛个数;请计算c1 至cN的和。对于上面这个例子,其和为:3 + 0 + 1 + 0 + 1 + 0 = 5。

输入
第1行:奶牛数N


第2行至N+1行:第i+1行包含一个整数,表示奶牛i的高度

输出
第1行:c1 至cN的累加和
样例输入
6
10
3
7
4
12
2
样例输出
5
全局题号
3058
提交次数
44
尝试人数
11
通过人数
4

Other language verions