AT_agc063_b [AGC063B] Insert 1, 2, 3, ...

称一个由正整数组成的数列 $a = (a_1, \ldots, a_n)$ **可生成**，是指可以从空序列出发，反复进行如下操作得到 $a$。 - 操作：选择一个正整数 $k$，并将 $(1, 2, \ldots, k-1, k)$ 插入到当前序列的任意位置。更形式化地说，对于当前序列 $a = (a_1, \ldots, a_m)$，选择一个整数 $i$ 满足 $0 \leq i \leq m$ 以及一个正整数 $k$，将 $a$ 替换为 $(a_1, \ldots, a_i, 1, 2, \ldots, k-1, k, a_{i+1}, \ldots, a_m)$。 例如，$a = (1,2,1,1,2,1,3,4,2,3)$ 是可生成的。以下是其中一种生成过程： $() \to (\mathbf{1,2}) \to (1,2,\mathbf{1,2,3}) \to (1,2,1,\mathbf{1,2,3,4},2,3) \to (1,2,1,1,2,\mathbf{1},3,4,2,3)$ ------ 给定一个由正整数组成的数列 $A = (A_1, \ldots, A_N)$。请你计算满足下列条件的整数对 $(L, R)$ 的个数： - $1 \leq L \leq R \leq N$，且连续子序列 $(A_L, \ldots, A_R)$ 是可生成的。

输入以如下格式从标准输入给出。 > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出满足条件的整数对 $(L, R)$ 的个数。

## 限制 - $1 \leq N \leq 5 \times 10^5$ - $1 \leq A_i \leq N$ ## 样例解释 1 共有以下 $11$ 个： - $(1,1),\ (1,2),\ (1,3),\ (1,4),\ (1,5),\ (1,6),\ (3,3),\ (3,4),\ (3,5),\ (3,6),\ (5,5)$ ## 样例解释 2 所有连续子序列都是可生成的。 由 ChatGPT 4.1 翻译