罗马尼亚贵族们众所周知，一个整数数组 $a[0], a[1], a[2], \dots, a[m - 1]$ 的“美感”（beauty）是指满足以下条件的正整数 $k$ 的数量：你可以将该数组划分为 $k$ 个互不相交的子数组（连续元素的序列），使得每个元素恰好包含在一个子数组中，且所有子数组都具有相同的“最小未出现值”（minimum excluded element，即 MEX）。一个整数数组的最小未出现值（MEX）是指未在数组中出现的最小严格正整数（大于 0）。

给你一个整数数组 $v[0], v[1], \dots, v[n - 1]$ 以及 $q$ 次询问，每次询问的形式为 $(l_i, r_i)$，其中对于所有 $0 \le i < q$，满足 $0 \le l_i \le r_i < n$。

对于每次询问，你需要求出子数组 $v[l_i], v[l_i + 1], \dots, 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 个整数的 std::vector，其中包含每次询问的答案。
• 对于每个测试用例，该函数恰好被调用一次。

数据范围

• $1 \le n \le 600\,000$
• $1 \le q \le 600\,000$
• $1 \le v[i] \le 400\,000$ 对于所有 $0 \le i < n$
• $0 \le l_i \le r_i < n$ 对于所有 $0 \le i < q$

子任务

• 1. (4 分) $1 \le n \le 10, 1 \le q \le 100$
• 1. (6 分) $1 \le n, q \le 100$
• 1. (17 分) $1 \le n, q \le 1\,000$
• 1. (10 分) $1 \le n, q \le 100\,000$ 且对于所有 $0 \le i < n$，有 $1 \le v[i] \le 2$
• 1. (30 分) $1 \le n, q \le 75\,000$
• 1. (33 分) 无附加限制。

样例

样例 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 行：n q
• 第 2 行：v[0] v[1] ... v[n - 1]
• 第 $3 + i$ 行（对于所有 $0 \le i < q$）：l_i r_i

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