#213799. [CEOI 2025] Equal Mex

It is well known among Romanian noblemen that the beauty of an integer array , , , , is the number of positive integers for which you can split the array into disjoint subarrays (sequences of consecutive elements) such that each element is contained in exactly one subarray and all the subarrays have the same minimum excluded element. The minimum excluded element of an integer array is the smallest strictly positive integer (greater than 0) that does not appear in the array.

You are given an integer array , , , and queries of the form , where for all .

For each query, you have to find the beauty of the array , , , .

Implementation Details

You should implement the following procedure:

std::vector<int> solve(
    int n, std::vector<int>& v,
    int q, std::vector<std::pair<int, int>>& queries);

• : the size of the integer array
• : array of length , the initial array
• : the number of queries
• : array of length describing the queries

This procedure should return a vector of integers containing the answer for each query. This procedure is called exactly once for each test case.

样例输入 1

10 2
1 1 2 2 3 3 1 2 3 4
1 6
1 9

样例输出 1

1
2

Constraints

• for all
• for all

Subtasks

1. (4 points)
2. (6 points)
3. (17 points)
4. (10 points) and for all
5. (30 points)
6. (33 points) No additional constraints.