P2866 [USACO06NOV] Bad Hair Day S
题目描述
农夫约翰有 n 头奶牛正在过乱头发节。这些奶牛站成一排,全部面朝同一个方向,并按照从队尾到队首的顺序依次编号为 1,2,…,n。其中编号为 n 的奶牛站在最前面,编号为 1 的奶牛站在最后面。第 i 头奶牛的身高为 hi。
因为所有奶牛都面朝前方,第 i 头奶牛只能看到编号比它大的奶牛,也就是排在它前面的奶牛。具体地,若 hi>hi+1,且 hi>hi+2,…,且 hi>hj,则称第 i 头奶牛能看到第 i+1,i+2,…,j 头奶牛。换言之,奶牛 i 能看到它前面连续的、身高严格小于 hi 的那些奶牛,一旦遇到一头身高不小于 hi 的奶牛,视线就会被挡住。
记 ci 为第 i 头奶牛能看到的奶牛数量,请求出 c1+c2+⋯+cn。
输入格式
第一行输入一个整数 n(1≦n≦8×104) 代表奶牛的数量。
此后 n 行,第 i 行输入一个整数 hi(1≦hi≦109) 代表第 i 头奶牛的身高。
输出格式
在一行上输出一个整数,代表 c1+c2+⋯+cn 的值。
测试样例
6
10
3
7
4
12
2
5
样例 1 解释
奶牛的身高依次为 10,3,7,4,12,2,逐头奶牛分析如下:
∙奶牛 1 身高为 10,能看到身高为 3,7,4 的奶牛 2,3,4,随后被身高为 12 的奶牛 5 挡住,因此 c1=3;
∙奶牛 2 身高为 3,它前面的奶牛 3 身高为 7,并不比它矮,因此 c2=0;
∙奶牛 3 身高为 7,能看到身高为 4 的奶牛 4,随后被奶牛 5 挡住,因此 c3=1;
∙奶牛 4 身高为 4,它前面的奶牛 5 身高为 12,并不比它矮,因此 c4=0;
∙奶牛 5 身高为 12,能看到身高为 2 的奶牛 6,因此 c5=1;
∙奶牛 6 前面没有奶牛,因此 c6=0。
总和为 3+0+1+0+1+0=5。
7
5
3
4
2
6
1
2
6
提示
答案可能超过 32 位带符号整数的表示范围,请使用 64 位整数保存答案。