Description

罗马尼亚贵族们普遍认为，一个整数数组 $a[0], a[1], a[2], \ldots, a[m - 1]$ 的美丽值定义为：满足以下条件的正整数 $k$ 的个数——你可以将该数组划分为 $k$ 个互不重叠的子数组（即连续元素的序列），使得：

1. 每个元素恰好属于一个子数组；
2. 所有子数组具有相同的最小缺失元素。

这里，一个整数数组的最小缺失元素是指数组中没有出现的、严格大于 $0$ 的最小正整数。

给定一个整数数组 $v[0], v[1], \ldots, v[n - 1]$，以及 $q$ 个询问，每个询问的形式为 $(l_i, r_i)$，其中对所有 $0 \leq i < q$，均有 $1 \leq l_i \leq r_i \leq n$。

对于每个询问，你需要求出数组 $v[l_i - 1], v[l_i ], \ldots, v[r_i - 1]$ 的美丽值。

实现细节

你需要实现如下过程：

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

• $n$：整数数组的长度；
• $v$：长度为 $n$ 的数组，即初始数组；
• $q$：询问的数量；
• $queries$：长度为 $q$ 的数组，表示各个询问。

该过程应返回一个长度为 $q$ 的数组，其中第 $i$ 个元素为第 $i$ 个询问的答案。该过程在每个测试用例中仅调用一次。

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

1
2

Hint

数据范围

• $1 \leq n \leq 600000$
• $1 \leq q \leq 600000$
• 对所有 $0 \leq i < n$，$1 \leq v[i] \leq 400000$
• 对所有 $0 \leq i < q$，$1 \leq l_i \leq r_i \leq n$

子任务

1. （4 分）$1 \leq n \leq 10,\ 1 \leq q \leq 100$
2. （6 分）$1 \leq n, q \leq 100$
3. （17 分）$1 \leq n, q \leq 1000$
4. （10 分）$1 \leq n, q \leq 100000$ 且对所有 $0 \leq i < n$，有 $1 \leq v[i] \leq 2$
5. （30 分）$1 \leq n, q \leq 75000$
6. （33 分）无额外限制

翻译由 ChatGPT-5 完成