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], \ldots, 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] \neq 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 5 \; 000 \; 000\)
• \(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.