#Algo0102. Bad Hair Day S

    ID: 66 Type: RemoteJudge 1000ms 125MiB Tried: 62 Accepted: 32 Difficulty: 3 Uploaded By: Tags>算法基础模拟数据结构luoguUSACO2006

Bad Hair Day S

题目描述

Famer John的一些牛中的 NN(1N80,000)(1 ≤ N ≤ 80,000) 正准备去参加坏头发节啦!因为每头牛对他们杂乱的发型都很在意,Famer John想要数出有多少牛能看到其他牛的脑袋。

每头牛都有一个指定的身高 hih_i (1hi109)(1 ≤ h_i ≤ 10^9) 并且它们都面朝东站成一排(图中是向右的)。因此,第 ii 头牛可以看到站在他前面的牛的脑袋,(也就是第i+1i+1, i+2i+2个牛等等),只要这些牛严格比第 ii 头牛矮就行。

比如这个例子:

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

牛牛们的朝向 -->

牛 #1 可以看见牛 #2, 3, 4 的发型.
牛 #2 看不见任何一头牛的发型.
牛 #3 可以看见牛 #4 的发型.
牛 #4 看不见任何一头牛的发型.
牛 #5 可以看见牛 #6 的发型.
牛 #6 压根看不见牛!

cic_i 表示从牛 ii 可以看见发型的牛的个数,请计算从 c1c_1cNc_N 的和。 例如, 样例的答案应该是 3+0+1+0+1+0=53 + 0 + 1 + 0 + 1 + 0 = 5.

输入格式

第一行为牛的总数 NN.

接下来的 NN 行: 第 i+1i+1 行包括一个整数,表示第 ii 头牛的身高。

输出格式

一行,从 c1c_1cNc_N 的和。

6
10
3
7
4
12
2
5