← 返回题目列表

AtCoder · abc436_f

I. 星空风景照片

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

从 AtCoder 星球看到的夜空中,有 N 星星,还有这些 N 星星从东到西排成一排。 的 i东方的第一颗星星 (1\le i\le N) 是 B _ i- 这些星星中最亮的。

高桥决定使用以下步骤拍摄夜空照片:

  1. 选择一对整数 (l,r) 满意 1\le l\le r\le N,并设置相机,以便 l-th, (l+1)-th, \ldots, r来自东方的第 颗星星全部进入框架,并且没有其他星星进入框架。
  2. 选择一个整数 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