Contest Duration: - (local time) (180 minutes) Back to Home
B - Insert 1, 2, 3, ... /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 操作：正整数 k を選び，列の好きな位置に (1, 2, \ldots, k-1, k) を挿入する．より形式的には，列 a = (a_1, \ldots, a_m) に対して 0\leq i\leq m となる整数 i および正整数 k を選び，a(a_1,\ldots,a_{i}, 1, 2, \ldots, k-1, k, a_{i+1}, \ldots, a_m) に置き換える．

() \to (\boldsymbol{1,2}) \to (1,2,\boldsymbol{1,2,3}) \to (1,2,1,\boldsymbol{1,2,3,4},2,3) \to (1,2,1,1,2,\boldsymbol{1},3,4,2,3)

• 1\leq L\leq R\leq N であり，連続部分列 (A_L, \ldots, A_R) は生成可能である．

### 制約

• 1\leq N\leq 5\times 10^5
• 1\leq A_i\leq N

N
A_1 \ldots A_N

6
1 2 1 2 1 3

### 出力例 1

11

• (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (3,3), (3,4), (3,5), (3,6), (5,5)

5
1 1 1 1 1

### 出力例 2

15

すべての連続部分列が生成可能です．

7
1 2 1 2 1 3 4

### 出力例 3

13

Score : 600 points

### Problem Statement

A sequence a = (a_1, \ldots, a_n) consisting of positive integers is said to be generatable when one can obtain a by repeating the following operation on an empty sequence.

• Operation: Choose a positive integer k, and insert (1, 2, \ldots, k-1, k) into some position in the sequence. More formally, for a sequence a = (a_1, \ldots, a_m), choose an integer i such that 0\leq i\leq m and a positive integer k, and replace a with (a_1,\ldots,a_{i}, 1, 2, \ldots, k-1, k, a_{i+1}, \ldots, a_m).

For instance, a = (1,2,1,1,2,1,3,4,2,3) is generatable. Here is one way to generate it:

() \to (\boldsymbol{1,2}) \to (1,2,\boldsymbol{1,2,3}) \to (1,2,1,\boldsymbol{1,2,3,4},2,3) \to (1,2,1,1,2,\boldsymbol{1},3,4,2,3).

You are given a sequence A = (A_1, \ldots, A_N) consisting of positive integers. Find the number of pairs of integers (L, R) such that:

• 1\leq L\leq R\leq N and the contiguous subsequence (A_L, \ldots, A_R) is generatable.

### Constraints

• 1\leq N\leq 5\times 10^5
• 1\leq A_i\leq N

### Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N

### Output

Print the number of pairs of integers (L, R) satisfying the conditions.

6
1 2 1 2 1 3

### Sample Output 1

11

Here are the 11 sought pairs:

• (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (3,3), (3,4), (3,5), (3,6), (5,5).

5
1 1 1 1 1

### Sample Output 2

15

All the contiguous subsequences are generatable.

7
1 2 1 2 1 3 4

13