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 翻译