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 one integer in a single line, the number of pairs $(l,r)$ that satisfy the conditions.

3
3 1 2 

3

5
3 2 1 2 3

5

7
2 1 3 1 2 3 4

8

Hint

Sample Explanation

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)$。

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $1\le N\le 10^6$；
• $1\le a_i\le N$。

Translated by ChatGPT 5