Ancient Problems Require Modern Solutions(Hard version!)
Tag(s):
No tags
Problem
Editorial
Analytics

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, 5th and 2nd person belong to the society with ID 2, and so on...

Now the watchman wants to find the position of Kth 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, 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$

SAMPLE INPUT
5 3
1 2 1 3 2
2 2 2 5
2 2 2 4
1 2 1 3

SAMPLE OUTPUT
5
-1
3

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...