注意事项

请在提交源代码前添加 #include "equalmex.h"。

题目描述

在罗马尼亚贵族中众所周知，一个整数数组 $a[0], a[1], a[2], \ldots, a[m-1]$ 的美感是正整数 $k$ 的数量，对于这些 $k$，你可以将数组分成 $k$ 个不相交的子数组（连续元素的序列），使得每个元素恰好包含在一个子数组中，并且所有子数组具有相同的最小排除元素。整数数组的最小排除元素是不出现在数组中的最小严格正整数（大于 $0$）。

给你一个整数数组 $v[0], v[1], \ldots, v[n-1]$ 和 $q$ 个查询，形式为 $(l_{i}, r_{i})$，其中对于所有 $0 \leq i < q$，$0 \leq l_{i} \leq r_{i} < n$。

对于每个查询，你需要找到数组 $v[l_{i}], v[l_{i}+1], \ldots, v[r_{i}]$ 的美感。

实现细节

你应该实现以下程序：

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$ 的整数向量，包含每个查询的答案。
• 对于每个测试点，该程序只被调用一次。

示例评测程序

示例评测程序读取以下格式的输入：

• 第 $1$ 行：$n\ q$
• 第 $2$ 行：$v[0]\ v[1]\ \ldots\ v[n-1]$
• 第 $3+i$ 行：$l_{i}\ r_{i}$ 对于所有 $0 \leq i < q$

并输出 $q$ 行，调用函数 solve 的结果，使用相应的参数。

样例 1

考虑以下调用：

solve(10, {1, 1, 2, 2, 3, 3, 1, 2, 3, 4}, 2, {{0, 5}, {0, 8}})

在这个样例中，$n=10$，有 $2$ 个查询，其中：

• $l_{0}=0$ 且 $r_{0}=5$
• $l_{1}=0$ 且 $r_{1}=8$

对于第一个查询，我们只能将区间分成一个子数组，从位置 $0$ 到位置 $5$。

对于第二个查询，$k$ 可以是 $1$ 或 $2$。

将区间分成 $1$ 个子数组的一种可能是选择从位置 $0$ 到位置 $8$ 的子数组。 将区间分成 $2$ 个子数组的一种可能是选择从位置 $0$ 到位置 $5$ 和从位置 $6$ 到位置 $8$ 的子数组。

第一个查询的答案是 $1$，第二个查询的答案是 $2$，因此调用 solve 将返回 $\{1, 2\}$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 600000$
• $1 \leq q \leq 600000$
• 对于所有 $0 \leq i < n$，$1 \leq v[i] \leq 400000$
• 对于所有 $0 \leq i < q$，$0 \leq l_{i} \leq r_{i} < n$

详细子任务附加限制及分值如下表所示。