P1823 [COI 2007] Patrik 音乐会的等待
题目描述
有 n 个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。
队伍中的人按照从队首到队尾的顺序依次编号为 1,2,…,n,第 i 个人的身高为 hi。
对于队伍中的任意两个人 a 和 b(a<b),若满足以下条件之一,则称他们可以互相看见:
∙他们相邻,即 b=a+1;
∙他们之间(不含第 a 个人与第 b 个人)没有任何一个人比他们中较矮的那一位更高,即对于所有满足 a<k<b 的 k,都有 hk≦min(ha,hb)。
请计算出有多少对人可以互相看见。
输入格式
第一行输入一个整数 n(1≦n≦5×105) 代表队伍中的人数。
此后 n 行,第 i 行输入一个整数 hi(1≦hi≦231−1) 代表第 i 个人的身高,单位为纳米(1 纳米等于 10−9 米)。
输出格式
在一行上输出一个整数,代表队伍中可以互相看见的人的对数。
测试样例
7
2
4
1
2
2
5
1
10
样例 1 解释
队伍中人的身高依次为 2,4,1,2,2,5,1。
相邻的 6 对人都可以互相看见,即 $\left(1, 2\right), \left(2, 3\right), \left(3, 4\right), \left(4, 5\right), \left(5, 6\right), \left(6, 7\right)$。
除此之外,还有 4 对不相邻的人可以互相看见:
∙(2,4):两人身高分别为 4 和 2,中间的第 3 个人身高为 1,不超过较矮的 2;
∙(2,5):两人身高分别为 4 和 2,中间的第 3,4 个人身高分别为 1,2,都不超过较矮的 2;
∙(2,6):两人身高分别为 4 和 5,中间的第 3,4,5 个人身高分别为 1,2,2,都不超过较矮的 4;
∙(4,6):两人身高分别为 2 和 5,中间的第 5 个人身高为 2,不超过较矮的 2。
例如 (1,3) 不能互相看见,因为第 1 个人身高为 2、第 3 个人身高为 1,而中间的第 2 个人身高为 4,比他们中较矮的 1 更高。
因此共有 6+4=10 对人可以互相看见。
6
3
1
2
2
4
1
9
提示
答案可能超过 32 位带符号整数的表示范围,请使用 64 位整数保存答案。