CF1227D2 Optimal Subsequences (Hard Version)

This is the harder version of the problem. In this version, $ 1 \le n, m \le 2\cdot10^5 $ . You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems. You are given a sequence of integers $ a=[a_1,a_2,\dots,a_n] $ of length $ n $ . Its subsequence is obtained by removing zero or more elements from the sequence $ a $ (they do not necessarily go consecutively). For example, for the sequence $ a=[11,20,11,33,11,20,11] $ : - $ [11,20,11,33,11,20,11] $ , $ [11,20,11,33,11,20] $ , $ [11,11,11,11] $ , $ [20] $ , $ [33,20] $ are subsequences (these are just some of the long list); - $ [40] $ , $ [33,33] $ , $ [33,20,20] $ , $ [20,20,11,11] $ are not subsequences. Suppose that an additional non-negative integer $ k $ ( $ 1 \le k \le n $ ) is given, then the subsequence is called optimal if: - it has a length of $ k $ and the sum of its elements is the maximum possible among all subsequences of length $ k $ ; - and among all subsequences of length $ k $ that satisfy the previous item, it is lexicographically minimal. Recall that the sequence $ b=[b_1, b_2, \dots, b_k] $ is lexicographically smaller than the sequence $ c=[c_1, c_2, \dots, c_k] $ if the first element (from the left) in which they differ less in the sequence $ b $ than in $ c $ . Formally: there exists $ t $ ( $ 1 \le t \le k $ ) such that $ b_1=c_1 $ , $ b_2=c_2 $ , ..., $ b_{t-1}=c_{t-1} $ and at the same time $ b_t

The first line contains an integer $ n $ ( $ 1 \le n \le 2\cdot10^5 $ ) — the length of the sequence $ a $ . The second line contains elements of the sequence $ a $ : integer numbers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ). The third line contains an integer $ m $ ( $ 1 \le m \le 2\cdot10^5 $ ) — the number of requests. The following $ m $ lines contain pairs of integers $ k_j $ and $ pos_j $ ( $ 1 \le k \le n $ , $ 1 \le pos_j \le k_j $ ) — the requests.

Print $ m $ integers $ r_1, r_2, \dots, r_m $ ( $ 1 \le r_j \le 10^9 $ ) one per line: answers to the requests in the order they appear in the input. The value of $ r_j $ should be equal to the value contained in the position $ pos_j $ of the optimal subsequence for $ k=k_j $ .

In the first example, for $ a=[10,20,10] $ the optimal subsequences are: - for $ k=1 $ : $ [20] $ , - for $ k=2 $ : $ [10,20] $ , - for $ k=3 $ : $ [10,20,10] $ .