1027: The Kth Time Query
[Creator : ]
Description
We have a sequence of $N$ numbers: $A = (a_1, a_2, …, a_N)$.
Process the $Q$ queries explained below:
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, …, a_N$. Which element will be the $k_i$-th occurence of the number $x_i$?
Print the index of that element, or $-1$ if there is no such element.
Input
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)$
- $0 \leq k_i \leq 10^9 (1 \leq i \leq Q)$
- All values in input are integers.
N Q a1 a2 ... aN x1 k1 x2 k2 ... xQ kQ
Output
Print Q lines. The i-th line should contain the answer to Query i.
Sample Input Copy
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 Copy
1
2
5
-1
3
6
-1
-1
HINT
Association List/Adjacency List