102352: [AtCoder]ABC235 C - The Kth Time Query

Problem Statement

We have a sequence of $N$ numbers: $A = (a_1, a_2, \dots, a_N)$.
Process the $Q$ queries explained below.

• Query $i$: You are given a pair of integers $(x_i, k_i)$. Let us look at the elements of $A$ one by one from the beginning: $a_1, a_2, \dots$ Which element will be the $k_i$-th occurrence of the number $x_i$?
  Print the index of that element, or $-1$ if there is no such element.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line should contain the answer to Query $i$.

Sample Input 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

Sample Output 1

1
2
5
-1
3
6
-1
-1

$1$ occurs in $A$ at $a_1, a_2, a_5$. Thus, the answers to Query $1$ through $4$ are $1, 2, 5, -1$ in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

问题描述

我们有一个包含$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$个出现？
  打印那个元素的索引，如果没有这样的元素则打印$-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$行。第$i$行应包含对查询$i$的回答。

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