self_describing

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, ..., b_{M-1}$ – an array in which for all $b_i$ it is true that the number $b_i$ appears 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, ..., b_{M-1}$ we define a “self-describing” subarray as a subarray $b_l, b_{l+1}, ..., b_r$ that is itself “self-describing”.

You are given an array $a_0, a_1, ..., 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, ..., 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,...,a_N$ and $Q$ queries $(l, r)$ in this order, calls your init and then outputs the answers your program gave to all query calls. You are free to modify the local grader.

Constraints and clarifications

• $1 \leq N, Q \leq 3 \cdot 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.

Example

stdin

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

stdout

3
2
5