第 K 次查询

题目描述

我们有一个长度为 $N$ 的数列 $A = (a_1, a_2, \dots, a_N)$。

请处理以下 $Q$ 个查询。

查询 $i$：给定一对整数 $(x_i, k_i)$。按顺序从前往后查看 $A$ 的元素 $a_1, a_2, \dots$，第 $k_i$ 次出现数字 $x_i$ 的元素是哪一个？

输出该元素的下标；如果不存在这样的元素，则输出 $-1$。

输入格式

输入按以下格式从标准输入给出：

$N$ $Q$
$a_1$ $a_2$ $\dots$ $a_N$
$x_1$ $k_1$
$x_2$ $k_2$
$\vdots$
$x_Q$ $k_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出查询 $i$ 的答案。

样例

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

1
2
5
-1
3
6
-1
-1

在 $A$ 中，$1$ 出现在 $a_1, a_2, a_5$。因此，查询 $1$ 到 $4$ 的答案依次为 $1, 2, 5, -1$。

3 2
0 1000000000 999999999
1000000000 1
123456789 1

2
-1

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $0 \le a_i \le 10^9$ $(1 \le i \le N)$
• $0 \le x_i \le 10^9$ $(1 \le i \le Q)$
• $1 \le k_i \le N$ $(1 \le i \le Q)$
• 输入中的所有值均为整数。