Ancient Problems Require Modern Solutions(Hard version!)

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.

Example:

Input:  5 3
1 2 1 3 2
2 2 2 5
2 2 2 4
1 2 1 3
Output: 5
-1
3

Approach

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class AncientProblems {
    public static void main(String args[]) throws Exception {

        Scanner st = new Scanner(System.in);
        int n = st.nextInt();
        int q = st.nextInt();

        long[] a = new long[n + 1];

        Map<Long, List<Integer>> map = new HashMap<>();
        List<Integer> s = null;
        for (int i = 1; i <= n; i++) {
            a[i] = st.nextLong();
            if (!map.containsKey(a[i])) {
                map.put(a[i], new ArrayList<>());
            }
            map.get(a[i]).add(i);
        }

        while (q > 0) {

            long d = st.nextLong();
            int k = st.nextInt();
            int l = st.nextInt();
            int r = st.nextInt();

            List<Integer> ls = map.get(d);
            int o = 0, c = 0;
            for (int i = 0; i < ls.size(); i++) {
                if (ls.get(i) >= l && ls.get(i) <= r) {
                    o++;
                    if (o == k) {
                        c = ls.get(i);
                        break;
                    }
                }
            }
            if (c == 0)
                System.out.println(-1);
            else
                System.out.println(c);

            q--;
        }

    }
}