[USACO06NOV] Bad Hair Day S

题目描述

农夫约翰有 $N$ 头奶牛正在过乱头发节。 每一头牛都站在同一排面朝右,它们被从左到右依次编号为 $1, 2, \cdots, N$。编号为 $i$ 的牛身高为 $h_i$。第 $N$ 头牛在最前面,而第 $1$ 头牛在最后面。 对于第 $i$ 头牛**前面**的第 $j$ 头牛,如果 $h_i>h_{i+1}, h_i>h_{i+2}, \cdots, h_i>h_j$,那么认为第 $i$ 头牛可以看到第 $i+1$ 到第 $j$ 头牛。 定义 $C_i$ 为第 $i$ 头牛所能看到的牛的数量。请帮助农夫约翰求出 $C _ 1 + C _ 2 + \cdots + C _ N$。

输入输出格式

输入格式


输入共 $N + 1$ 行。 第一行为一个整数 $N$,代表牛的个数。 接下来 $N$ 行,每行一个整数 $a _ i$,分别代表第 $1, 2, \cdots, N$ 头牛的身高。

输出格式


输出共一行一个整数,代表 $C _ 1 + C _ 2 + \cdots + C _ N$。

输入输出样例

输入样例 #1

6
10
3
7
4
12
2

输出样例 #1

5

说明

### 数据规模与约定 对于 $100\%$ 的数据,保证 $1 \leq N \leq 8 \times 10 ^ 4$,$1 \leq h _ i \leq 10 ^ 9$。