C - 第K个查询

分值: $300$ 分

问题描述

给定一个长度为$N$的序列$A = (a_1, a_2, \dots, a_N)$。按照下面的方式对$Q$次查询进行处理。

• 查询$i$：给定一对整数$(x_i, k_i)$。依次从序列$A$的开头查看元素 $a_1, a_2, \dots$。第$i$次查询要找到数字$x_i$在序列$A$中的第$k_i$次出现的位置。如果不存在这样的元素，输出-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)$
• 所有输入值均为整数。

输入

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

$N$ $Q$

$a_1$ $a_2$ $\dots$ $a_N$

$x_1$ $k_1$

$x_2$ $k_2$

$\vdots$

$x_Q$ $k_Q$

输出

输出应包含$Q$行，每行为对应查询的答案。

示例

输入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

解释：数字1在序列$A$中出现在位置$a_1, a_2, a_5$，所以第1个查询到第4个查询分别的答案为1, 2, 5, -1。

输入2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

输出2

2
-1