SOLVE
LATER
Problem Statement is same in both version.They differ only in constraints.
There are N People standing in a Queue to pay their Internet bill. Each of them belongs to some Society. For Example,
if \(N = 5\) and \({[1,2,1,3,2]}\) then the 1st, 3rd^{ }person belong to the same society with ID 1, 5^{th }and 2nd person belong to the society with ID 2, and so on...
Now the watchman wants to find the position of K^{th }Person of Society with ID D, between the range \([L,R]\), if no such person exists then print -1.
You have to Answer Q queries.
For Example if \(N = 5\) and \({[1,2,1,3,2]}\) is the array of persons and \(D = 2\), \(K = 2\), and the Range is \([2,5]\), then the answer will be 5.
If the Range would be \([2,4]\), then the answer would be -1, as only one person with ID 2 is present in this range.
Example 2 - if \(N = 5\) and \([1,2,3,1,2]\) is the array of persons then
For \(D = 2\) and \(K = 2\) and range is \([3, 5]\) the answer will be -1 as there is only one person with \(D = 2\) but if the range is \([2,5]\) for the same D and K value, the answer will be 5 as 2nd person with ID = 2 in this range is at 5th position (1 based index).
INPUT
First-line contains integer N and Q;
Next line contains N space-separated integers A[1], A[2]....A[n] respectively.
Next, Q line contains Four Integers \(D \; K \; L \; R\)
OUTPUT
For each independent test cases print the required position of the person if exists otherwise print -1 in a new line.
CONSTRAINS
\(2 \leq N,Q \leq 10^5 \\ 1 \leq Ai \leq 10^6 \\ 1 \leq k \leq N \\ 1 \leq D \leq 10^6 \\ 1 \leq L < R \leq N\)