#216437. [IATI 2025] 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 -- an array in which for all it is true that the number appears times in the entire array. , , are all examples of "self-describing" arrays, while (there is only one occurrence of ), (there are occurrences of ) are all examples of non-"self-describing" arrays.

Additionally for an array we define a "self-describing" subarray as a subarray that is itself "self-describing".

You are given an array and queries such that . For each query you should find the number of "self-describing" subarrays for which 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 values in this order.

long long query(int l, int r)

This function will be called times per test and will correspond to a query for the range , 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 , , and queries in this order, calls your and then outputs the answers your program gave to all calls. You are free to modify the local grader.

样例输入 1

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

样例输出 1

3
2
5

Constraints

• for all
• for all queries.

Subtasks

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