#910. [USACO2006NOV] Bad Hair Day S 乱头发节

[USACO2006NOV] Bad Hair Day S 乱头发节

题目描述

农夫约翰有 N(N≤80000)N (N \leq 80000) 头奶牛正在过乱头发节。每一头牛都站在同一列面朝东方,而且每一头牛的身高为 hih_i。第 NN 头牛在最前面,而第 11 头牛在最后面。

对于第 ii 头牛前面的第 jj 头牛,如果hi>hi+1h_i>h_{i+1}并且hi>hi+2,h_i>h_{i+2}, ⋯ ,\cdots, hi>hjh_i>h_j,那么认为第 ii 头牛可以看到第 i+1i+1 到第 jj 头牛的头发。

定义 CiC_i 为第 ii 头牛所能看到的别的牛的头发的数量。请帮助农夫约翰求出 ∑i=1nCi\sum_{i=1}^n C_i

输入格式

第一行:N

接下来 N 行,每行一个整数 hi

输出格式

一个整数,表示 ∑i=1nCi\sum_{i=1}^n C_i

样例输入

6
5
2
4
2
6
1

样例输出 #1

5