Subpermutations

Description

You are given an array of $A$ consisting of $N$ integers, indexed from $0$ to $N-1$. It is known that every element of $A$ is an integer between $1$ and $N$. A subarray $(l,r)$ $(0\le l\le r<N)$ of the array $A$ is defined as the array $[A[l],A[l+1],\dots ,A[r]]$.

An array $b$ consisting of $m$ integers indexed from $0$ to $m-1$ is a permutation if it contains all the integers from $1$ to $m$ in any order. In other words, for all $0\le i<j<m$, $b[i]\ne b[j]$ and for all $1\le x\le m$, there exists $0\le i\le m-1$ such that $b[i]=x$.

Your task is to find the number of subarrays of $A$ that are permutations.

Implementation Details

You should implement the following procedure.

long long count_subperm(int N, std::vector<int> A)

• $N$: The length of the array $A$.
• $A$: An array of integers consisting of $N$ integers.
• This procedure should return one integer containing the number of subarrays of $A$ that are a permutation.
• This procedure is called exactly once for each test case.

Constraints

• $1\le N\le 5000000$
• $1\le A[i]\le N$ for each $i$ such that $0\le i<N$

Subtasks

Examples

Example 1

Consider the following call.

count_subperm(3, [3, 1, 2])	

For this example, the subarrays of $A$ that are permutations are as follows.

1. The subarray $(1,1)$, which is the array $[1]$. It has only one distinct element and contains all the integers from $1$ to $1$.
2. The subarray $(1,2)$, which is the array $[1,2]$. It has two distinct elements and contains all the integers from $1$ to $2$.
3. The subarray $(0,2)$, which is the array $[3,1,2]$. It has three distinct elements and contains all the integers from $1$ to $3$.

Therefore, the procedure should return $3$.

Example 2

Consider the following call.

count_subperm(5, [3, 2, 1, 2, 3])	

For this example, the subarrays of $A$ that are permutations are as follows.

1. The subarray $(2,2)$, which is the array $[1]$. It has only one distinct element and contains all the integers from $1$ to $1$.
2. The subarray $(2,3)$, which is the array $[1,2]$. It has two distinct elements and contains all the integers from $1$ to $2$.
3. The subarray $(1,2)$, which is the array $[2,1]$. It has two distinct elements and contains all the integers from $1$ to $2$.
4. The subarray $(0,2)$, which is the array $[3,2,1]$. It has three distinct elements and contains all the integers from $1$ to $3$.
5. The subarray $(2,4)$, which is the array $[1,2,3]$. It has three distinct elements and contains all the integers from $1$ to $3$.

Therefore, the procedure should return $5$.

Example 3

Consider the following call.

count_subperm(7, [2, 1, 3, 1, 2, 3, 4])	

For this example, the subarrays of $A$ that are permutations are as follows.

1. The subarray $(1,1)$, which is the array $[1]$. It has only one distinct element and contains all the integers from $1$ to $1$.
2. The subarray $(3,3)$, which is the array $[1]$. It has only one distinct element and contains all the integers from $1$ to $1$.
3. The subarray $(0,1)$, which is the array $[2,1]$. It has two distinct elements and contains all the integers from $1$ to $2$.
4. The subarray $(3,4)$, which is the array $[1,2]$. It has two distinct elements and contains all the integers from $1$ to $2$.
5. The subarray $(0,2)$, which is the array $[2,1,3]$. It has three distinct elements and contains all the integers from $1$ to $3$.
6. The subarray $(2,4)$, which is the array $[3,1,2]$. It has three distinct elements and contains all the integers from $1$ to $3$.
7. The subarray $(3,5)$, which is the array $[1,2,3]$. It has three distinct elements and contains all the integers from $1$ to $3$.
8. The subarray $(3,6)$, which is the array $[1,2,3,4]$. It has four distinct elements and contains all the integers from $1$ to $4$.

Therefore, the procedure should return $8$.

Sample Grader

Input Format:

N
A[0] A[1] ... A[N - 1]

Output Format:

C

Here, $C$ is the integer returned by count_subperm.