题目描述

给出一个长度为 $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$ ... $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

3 2
0 1000000000 999999999
1000000000 1
123456789 1

2
-1

样例1解释

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

数据范围

$1 \leq N,Q \leq 2 \times 10^5$
$0 \leq a_i,x_i \leq 10^9$ $(1 \leq i \leq N)$
$1 \leq k_i \leq N$ $(1 \leq i \leq Q)$
输入中的所有值都是整数。

来源

• AtCoder ABC235C