Problem Background

Translated from Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D2T2. $\texttt{1s,0.5G}$.

Happy Birthday to NaCly_Fish! (2024.7.28)

Problem Description

Given a sequence \(a\) of length \(N\), find the number of pairs \((l, r)\) that satisfy the following conditions:

• \(1 \le l \le r \le N\);
• \(a_l, a_{l+1}, \cdots, a_{r-1}, a_r\) is a permutation of \(1 \sim r-l+1\).

Input Format

The first line contains a positive integer \(N\), representing the length of the sequence.

The second line contains \(N\) positive integers, describing the sequence \(a\).

Output Format

Output a single integer, which is the number of pairs \((l, r)\) that meet the conditions.

Sample Input and Output

Sample Input #1

3
3 1 2

Sample Output #1

3

Sample Input #2

5
3 2 1 2 3

Sample Output #2

5

Sample Input #3

7
2 1 3 1 2 3 4

Sample Output #3

8

Notes

Sample Explanation

For Sample 3: The pairs \((l, r)\) that satisfy the conditions are \((2,2), (1,2), (1,3), (4,4), (4,5), (4,6), (4,7), (3,5)\).

Data Range

For \(100\%\) of the data, it is guaranteed that:

• \(1 \le N \le 10^6\);
• \(1 \le a_i \le N\).

见题面 Input 部分

见题面 Output 部分