AT_abc436_f.[ABC436F] Starry Landscape Photo

在 AtCoder 星球的夜空中，有 $N$ 颗星星，这 $N$ 颗星星从东到西排成一条直线。从东边数第 $i$ 颗星星（$1 \leq i \leq N$）是这些星星中第 $B_i$ 亮的。

高桥决定用如下方法拍摄这片夜空：

1. 选择一对整数 $(l, r)$，满足 $1 \leq l \leq r \leq N$，调整相机使得从东边数第 $l$ 颗、第 $l+1$ 颗，…，第 $r$ 颗星星都正好进入画面，且画面中没有其它星星。
2. 选择一个整数 $b$，满足 $1 \leq b \leq N$，打开快门，使这 $N$ 颗星星中亮度排名第 $1$ 到第 $b$ 的星星（且位于画面中的部分）被捕捉到，且没有其它星星被捕捉到。

不过，如果根本没有星星被捕捉到，则不能算作一次拍摄。

请你求出，通过上述方法所能拍摄到的不同星星集合的数目。

输入由标准输入给出，格式如下：

$N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出答案。

样例解释 1

例如，取 $(l, r) = (2, 4), b=3$ 时，可以拍到两颗星：从东边数第 $2$ 颗星和第 $4$ 颗星。

算上这个情况，共有以下 $12$ 种不同的星星集合。在每种拍摄中，极东的星星排列在最左侧，亮度第 $i$ 亮的星星用整数 $i$ 标记。

不存在其他可捕捉的星星集合，所以请输出 12。

数据范围

• $1\leq N\leq5\times10^5$
• $1\leq B_i\leq N\ (1\leq i\leq N)$
• $B_i\neq B_j\ (1\leq i<j\leq N)$
• 所有输入值均为整数。

由 ChatGPT 5 翻译