LG#P1823. [COI 2007] Patrik 音乐会的等待

[COI 2007] Patrik 音乐会的等待

P1823 [COI 2007] Patrik 音乐会的等待

题目描述

\hspace{15pt}有 nn 个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。

\hspace{15pt}队伍中的人按照从队首到队尾的顺序依次编号为 1,2,…,n1, 2, \dots, n,第 ii 个人的身高为 hih_i。

\hspace{15pt}对于队伍中的任意两个人 aa 和 b(a<b)b \left(a < b\right),若满足以下条件之一,则称他们可以互相看见:

∙ \hspace{23pt}\bullet\,他们相邻,即 b=a+1b = a+1;

∙ \hspace{23pt}\bullet\,他们之间(不含第 aa 个人与第 bb 个人)没有任何一个人比他们中较矮的那一位更高,即对于所有满足 a<k<ba < k < b 的 kk,都有 hk≦min⁡(ha,hb)h_k \leqq \min\left(h_a, h_b\right)。

\hspace{15pt}请计算出有多少对人可以互相看见。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦5×105)n \left(1 \leqq n \leqq 5 \times 10^5\right) 代表队伍中的人数。

\hspace{15pt}此后 nn 行,第 ii 行输入一个整数 hi(1≦hi≦231−1)h_i \left(1 \leqq h_i \leqq 2^{31}-1\right) 代表第 ii 个人的身高,单位为纳米(11 纳米等于 10−910^{-9} 米)。

输出格式

\hspace{15pt}在一行上输出一个整数,代表队伍中可以互相看见的人的对数。

测试样例

7
2
4
1
2
2
5
1
10

样例 1 解释

\hspace{15pt}队伍中人的身高依次为 2,4,1,2,2,5,12, 4, 1, 2, 2, 5, 1。

\hspace{15pt}相邻的 66 对人都可以互相看见,即 $\left(1, 2\right), \left(2, 3\right), \left(3, 4\right), \left(4, 5\right), \left(5, 6\right), \left(6, 7\right)$。

\hspace{15pt}除此之外,还有 44 对不相邻的人可以互相看见:

∙ (2,4)\hspace{23pt}\bullet\,\left(2, 4\right):两人身高分别为 44 和 22,中间的第 33 个人身高为 11,不超过较矮的 22;

∙ (2,5)\hspace{23pt}\bullet\,\left(2, 5\right):两人身高分别为 44 和 22,中间的第 3,43, 4 个人身高分别为 1,21, 2,都不超过较矮的 22;

∙ (2,6)\hspace{23pt}\bullet\,\left(2, 6\right):两人身高分别为 44 和 55,中间的第 3,4,53, 4, 5 个人身高分别为 1,2,21, 2, 2,都不超过较矮的 44;

∙ (4,6)\hspace{23pt}\bullet\,\left(4, 6\right):两人身高分别为 22 和 55,中间的第 55 个人身高为 22,不超过较矮的 22。

\hspace{15pt}例如 (1,3)\left(1, 3\right) 不能互相看见,因为第 11 个人身高为 22、第 33 个人身高为 11,而中间的第 22 个人身高为 44,比他们中较矮的 11 更高。

\hspace{15pt}因此共有 6+4=106+4=10 对人可以互相看见。

6
3
1
2
2
4
1
9

提示

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