题目描述

It is well known among Romanian noblemen that the beauty of an integer array $a[0]$, $a[1]$, $a[2]$, $\ldots$, $a[m-1]$ is the number of positive integers $k$ for which you can split the array into $k$ 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 $v[0]$, $v[1]$, $\ldots$, $v[n-1]$ and $q$ queries of the form $(l_i, r_i)$, where $1 \leq l_i \leq r_i \leq n$ for all $0 \leq i < q$.

For each query, you have to find the beauty of the array $v[l_i - 1]$, $v[l_i]$, $\ldots$, $v[r_i - 1]$.

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);

• $n$: the size of the integer array
• $v$: array of length $n$, the initial array
• $q$: the number of queries
• $queries$: array of length $q$ describing the queries

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

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

1
2

提示

Constraints

• $1 \leq n \leq 600000$
• $1 \leq q \leq 600000$
• $1 \leq v[i] \leq 400000$ for all $0 \leq i < n$
• $1 \leq l_i \leq r_i \leq n$ for all $0 \leq i < q$

Subtasks

1. (4 points) $1 \leq n \leq 10, 1 \leq q \leq 100$
2. (6 points) $1 \leq n, q \leq 100$
3. (17 points) $1 \leq n, q \leq 1000$
4. (10 points) $1 \leq n, q \leq 100000$ and $1 \leq v[i] \leq 2$ for all $0 \leq i < n$
5. (30 points) $1 \leq n, q \leq 75000$
6. (33 points) No additional constraints.