题目描述

長さ $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$ に対する答えを出力せよ。

题目大意

给出一个长度为 $n$ 的序列 $a_1,a_2,..,a_n$ 并给出 $q$ 次询问。对于第 $i$ 次询问（ $1≤i≤q$ ）会给出两个数 $x_i$ 和 $k_i$ ，此时请输出 $x_i$ 在序列 $a$ 中第 $k_i$ 次出现时元素的下标。若 $x_i$ 在 $a$ 中的出现次数不足 $k_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
2
5
-1
3
6
-1
-1

3 2
0 1000000000 999999999
1000000000 1
123456789 1

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)$
• 入力はすべて整数である。

Sample Explanation 1

$A$ の中で $1$ は $a_1,\ a_2,\ a_5$ に登場します。よって、クエリ $1$ からクエリ $4$ の答えは順に $1,\ 2,\ 5,\ -1$ となります。