Problem Description

Elena is yet again tasked with solving a problem involving subarrays with a special property. By now she finds these tasks banal, so she leaves writing a solution to you -- the IATI contestants. The problem statement is as follows:

We define a "self-describing" array $b_0, b_1, \dots, b_{M-1}$ -- an array in which for all $b_i$ it is true that the number $b_i$ appears $\textit{exactly}$ $b_i$ times in the entire array. $[1, 2, 2]$, $[5,5,5,5,5]$, $[3,1,3,2,3,2]$ are all examples of "self-describing" arrays, while $[100, 1, 2, 2]$ (there is only one occurrence of $100$), $[1,1,1,1,1]$ (there are $5$ occurrences of $1$) are all examples of non-"self-describing" arrays.

Additionally for an array $b_0, b_1, \dots, b_{M-1}$ we define a "self-describing" subarray as a subarray $b_l, b_{l+1} \dots b_r$ that is itself "self-describing".

You are given an array $a_0, a_1, \dots, a_{N-1}$ and $Q$ queries $(l,r)$ such that $l \leq r$. For each query you should find the number of "self-describing" subarrays $(l', r')$ for which $l \leq l' \leq r' \leq r$ for all queries.

Implementation details

You should implement the following two procedures:

void init(int N, int Q, const std::vector<int>& a)

This function will be called once per test and provides your program with the original array as a vector, consisting of the $N$ values $a_0, a_1, \dots a_{N-1}$ in this order.

long long query(int l, int r)

This function will be called $Q$ times per test and will correspond to a query for the range $(l, r)$, it should return the answer to that query.

Local testing

To test your program locally, a local grader and a header file are provided. The local grader reads $N$, $Q$, $a_1, a_2, \dots, a_N$ and $Q$ queries $(l, r)$ in this order, calls your $\verb|init|$ and then outputs the answers your program gave to all $\verb|query|$ calls. You are free to modify the local grader.

7 3
1 2 1 2 3 3 3
0 3
2 6
0 6

3
2
5

Hint

Constraints

• $1 \leq N, Q \leq 3 \times 10^5$
• $1 \leq a_i \leq N$ for all $0 \leq i \leq N - 1$
• $0 \leq l \leq r \leq N - 1$ for all queries.

Subtasks

The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.