A Little Bit of Formal Statements Never Hurt Anybody

题目描述

给定一个由两两不同的整数组成的数组 $a_1,a_2,\dots,a_n$。

请统计满足以下条件的数对 $(l,r)$ 的数量：

• $1\le l\le r\le n$；
• 设 $k$ 是区间 $a_l,a_{l+1},\dots,a_r$ 中最大元素所在的位置；
• 满足

输入格式

第一行包含一个整数 $n$（$1\le n\le 3\cdot 10^5$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$-10^9\le a_i\le 10^9$），表示数组 $a$ 的元素。

保证数组中的所有整数两两不同。

输出格式

输出一个整数，表示题目所描述的数对 $(l,r)$ 的数量。

输入输出样例 #1

输入 #1

5
1 3 5 4 9

输出 #1

6

评分方式

1. $3$ 分：$n\le 100$；
2. $7$ 分：$n\le 10^3$；
3. $13$ 分：$a_1<a_2<\dots<a_n$；
4. $8$ 分：存在 $i$（$1\le i\le n$），使得 $a_1<\dots<a_i$ 且 $a_i>\dots>a_n$；
5. $22$ 分：$n\le 10^5$；
6. $23$ 分：数组由随机整数构成（$-10^9\le a_i\le 10^9$）；
7. $24$ 分：无额外限制。