LG#P2866. 乱头发节

乱头发节

P2866 [USACO06NOV] Bad Hair Day S

题目描述

\hspace{15pt}农夫约翰有 nn 头奶牛正在过乱头发节。这些奶牛站成一排,全部面朝同一个方向,并按照从队尾到队首的顺序依次编号为 1,2,…,n1, 2, \dots, n。其中编号为 nn 的奶牛站在最前面,编号为 11 的奶牛站在最后面。第 ii 头奶牛的身高为 hih_i。

\hspace{15pt}因为所有奶牛都面朝前方,第 ii 头奶牛只能看到编号比它大的奶牛,也就是排在它前面的奶牛。具体地,若 hi>hi+1h_i > h_{i+1},且 hi>hi+2h_i > h_{i+2},…\dots,且 hi>hjh_i > h_j,则称第 ii 头奶牛能看到第 i+1,i+2,…,ji+1, i+2, \dots, j 头奶牛。换言之,奶牛 ii 能看到它前面连续的、身高严格小于 hih_i 的那些奶牛,一旦遇到一头身高不小于 hih_i 的奶牛,视线就会被挡住。

\hspace{15pt}记 cic_i 为第 ii 头奶牛能看到的奶牛数量,请求出 c1+c2+⋯+cnc_1 + c_2 + \dots + c_n。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦8×104)n \left(1 \leqq n \leqq 8 \times 10^4\right) 代表奶牛的数量。

\hspace{15pt}此后 nn 行,第 ii 行输入一个整数 hi(1≦hi≦109)h_i \left(1 \leqq h_i \leqq 10^9\right) 代表第 ii 头奶牛的身高。

输出格式

\hspace{15pt}在一行上输出一个整数,代表 c1+c2+⋯+cnc_1 + c_2 + \dots + c_n 的值。

测试样例

6
10
3
7
4
12
2
5

样例 1 解释

\hspace{15pt}奶牛的身高依次为 10,3,7,4,12,210, 3, 7, 4, 12, 2,逐头奶牛分析如下:

∙ \hspace{23pt}\bullet\,奶牛 11 身高为 1010,能看到身高为 3,7,43, 7, 4 的奶牛 2,3,42, 3, 4,随后被身高为 1212 的奶牛 55 挡住,因此 c1=3c_1=3;

∙ \hspace{23pt}\bullet\,奶牛 22 身高为 33,它前面的奶牛 33 身高为 77,并不比它矮,因此 c2=0c_2=0;

∙ \hspace{23pt}\bullet\,奶牛 33 身高为 77,能看到身高为 44 的奶牛 44,随后被奶牛 55 挡住,因此 c3=1c_3=1;

∙ \hspace{23pt}\bullet\,奶牛 44 身高为 44,它前面的奶牛 55 身高为 1212,并不比它矮,因此 c4=0c_4=0;

∙ \hspace{23pt}\bullet\,奶牛 55 身高为 1212,能看到身高为 22 的奶牛 66,因此 c5=1c_5=1;

∙ \hspace{23pt}\bullet\,奶牛 66 前面没有奶牛,因此 c6=0c_6=0。

\hspace{15pt}总和为 3+0+1+0+1+0=53+0+1+0+1+0=5。

7
5
3
4
2
6
1
2
6

提示

\hspace{15pt}答案可能超过 3232 位带符号整数的表示范围,请使用 6464 位整数保存答案。