この問題は 連想配列 と呼ばれるデータ構造を利用することで効率よく解くことができる問題です。

キーを「\(A\) に登場する整数」、値を「 \(A\) に登場した場所が昇順に入っている配列」とした連想配列を用意しましょう。
たとえば \(N = 6, A = (1, 1, 2, 3, 1, 2)\) の場合は、データ構造の名前を \(m\) として

\[ \begin{aligned} m\lbrack 1 \rbrack &= \lbrace 1, 2, 5 \rbrace \\ m \lbrack 2 \rbrack &= \lbrace 3, 6 \rbrace \\ m \lbrack 3 \rbrack &= \lbrace 4 \rbrace \end{aligned} \]

というような連想配列が構成されます。

上記の連想配列があればクエリを高速に処理することができます。
具体的なアルゴリズムとしては、\((x, k)\) を要素とするクエリが飛んできた場合に以下の操作を行います。

• \(m\lbrack x \rbrack\) およびその長さを参照する。
  • \(m \lbrack x \rbrack\) の長さが \(k\) 以上の場合は、 \(m\lbrack x \rbrack\) の前から \(k\) 番目の要素を出力する。
  • \(m \lbrack x \rbrack\) の長さが \(k\) 未満の場合は、\(-1\) を出力する。

計算量は連想配列の要素を検索する計算量を \(T\) として \(\mathrm{O}((N + Q)T)\) です。たとえば C++ の std::map の場合は \(T = \mathrm{O}(\log N)\) なので全体の計算量は \(\mathrm{O}((N + Q)\log N)\) になります。

Python による実装例は次の通りです。

from collections import defaultdict

N, Q = map(int, input().split())
A = list(map(int, input().split()))

m = defaultdict(list)
for i in range(N):
  m[A[i]].append(i + 1)

for _ in range(Q):
  x, k = map(int, input().split())
  if k <= len(m[x]):
    print(m[x][k - 1])
  else:
    print(-1)