分数: 500 点
问题陈述
从 AtCoder 星球看到的夜空中,有 N 星星,还有这些 N 星星从东到西排成一排。 的 i东方的第一颗星星 (1\le i\le N) 是 B _ i- 这些星星中最亮的。
高桥决定使用以下步骤拍摄夜空照片:
- 选择一对整数 (l,r) 满意 1\le l\le r\le N,并设置相机,以便 l-th, (l+1)-th, \ldots, r来自东方的第 颗星星全部进入框架,并且没有其他星星进入框架。
- 选择一个整数 b 满意 1\le b\le N,然后打开快门,让所有星星都在其中 N 恒星的亮度排名为 1st 通过 b-th(并且适合框架)被捕获,并且没有其他星星被捕获。
但是,他可能不会拍摄没有捕捉到星星的照片。
求以这种方式拍摄的照片中可以捕捉到的不同星星组的数量。
约束
- 1\le N\le5\times10 ^ 5
- 1\le B _ i\le N\ (1\le i\le N)
- B _ i\ne B _ j\ (1\le i\lt j\le N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N B _ 1 B _ 2 \ldots B _ N
输出
打印答案。
示例输入 1
4 3 1 4 2
示例输出 1
12
例如, (l,r)=(2,4),b=3,您可以拍摄两颗星星的照片: 2东方和东方的第二颗星 4来自东方的第三颗星。
包括这个在内,您可以用以下方式拍照 12 不同的星星组。 在每张图片中,更东边的星星排列在更左边,而 i- 第一颗最亮的星星用整数标记 i.

无法捕获其他集合,因此打印 12.
示例输入 2
7 1 2 3 4 5 6 7
示例输出 2
28
示例输入 3
20 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
示例输出 3
627