题目描述

称一个由正整数组成的数列 $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

输入

6
1 2 1 2 1 3

输出

11

样例 2

输入

5
1 1 1 1 1

输出

15

样例 3

输入

7
1 2 1 2 1 3 4

输出

13

说明/提示

限制

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