← 返回题目列表

AtCoder · abc235_c

F. 第K次时间查询

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

我们有一系列 N 号码: A = (a_1, a_2, \dots, a_N).
处理 Q 查询解释如下。

  • 查询 i:给你一对整数 (x_i, k_i)。让我们看看其中的要素 A 从头开始一一: a_1, a_2, \dots 哪个元素将是 k_i- 数字第 1 次出现 x_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 at 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