The Kth Time Query

题目描述

有一个长度为 $N$ 的数列 $A = (a_1, a_2, \dots, a_N)$。
请回答下面描述的 $Q$ 个查询。

• 查询 $i$：给定整数对 $(x_i, k_i)$。从前往后依次查看 $A$ 的元素 $a_1, a_2, \dots$，请输出数 $x_i$ 第 $k_i$ 次出现时是在 $A$ 的第几个元素。如果不存在满足条件的元素，则输出 $-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$ 个查询的答案。

输入输出样例 #1

输入 #1

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

1
2
5
-1
3
6
-1
-1

输入输出样例 #2

输入 #2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

输出 #2

2
-1

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^9$（$1 \leq i \leq N$）
• $0 \leq x_i \leq 10^9$（$1 \leq i \leq Q$）
• $1 \leq k_i \leq N$（$1 \leq i \leq Q$）
• 所有输入均为整数。

样例解释 1

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