D2. Optimal Subsequences (Hard Version)

This is the harder version of the problem. In this version, 1≤n,m≤2?105. 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=[a1,a2,…,an] 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≤k≤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=[b1,b2,…,bk] is lexicographically smaller than the sequence c=[c1,c2,…,ck] if the first element (from the left) in which they differ less in the sequence b than in c. Formally: there exists t (1≤t≤k) such that b1=c1, b2=c2, ..., bt?1=ct?1 and at the same time bt<ct. For example:

[10,20,20] lexicographically less than [10,21,1],
[7,99,99] is lexicographically less than [10,21,1],
[10,21,0] is lexicographically less than [10,21,1].
You are given a sequence of a=[a1,a2,…,an] and m requests, each consisting of two numbers kj and posj (1≤k≤n, 1≤posj≤kj). For each query, print the value that is in the index posj of the optimal subsequence of the given sequence a for k=kj.

For example, if n=4, a=[10,20,30,20], kj=2, then the optimal subsequence is [20,30] — it is the minimum lexicographically among all subsequences of length 2 with the maximum total sum of items. Thus, the answer to the request kj=2, posj=1 is the number 20, and the answer to the request kj=2, posj=2 is the number 30.

Input

The first line contains an integer n (1≤n≤2?105) — the length of the sequence a.

The second line contains elements of the sequence a: integer numbers a1,a2,…,an (1≤ai≤109).

The third line contains an integer m (1≤m≤2?105) — the number of requests.

The following m lines contain pairs of integers kj and posj (1≤k≤n, 1≤posj≤kj) — the requests.

Output

Print m integers r1,r2,…,rm (1≤rj≤109) one per line: answers to the requests in the order they appear in the input. The value of rj should be equal to the value contained in the position posj of the optimal subsequence for k=kj.

Examples

input
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3
output
20
10
20
10
20
10
input
7
1 2 1 3 1 2 1
9
2 1
2 2
3 1
3 2
3 3
1 1
7 1
7 7
7 4
output
2
3
2
3
2
3
1
1
3

Note

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].

題意

給你n個數(shù)，定義長度為k的理想序列為當(dāng)前k個數(shù)和最大的子序列，且這個子序列的字典序要最小。

然后現(xiàn)在給你q個詢問，每次問你長度為ki的理想序列的第pos個數(shù)是什么

題解

理想序列的構(gòu)成，顯然是貪心的，每次放最大的字典序最小的數(shù)進(jìn)去。

我們將詢問離線之后，難點就變成如何求第k個數(shù)是多少，實際上這個就是典型的離線求第k大的題目。。。做法非常多，我才用的是樹狀數(shù)組的二分，這個復(fù)雜度是logn^2的，線段樹上2分是logn的，這個我就懶得寫了。

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
int a[maxn],index[maxn],ans[maxn],sum[maxn];
int n;
int lowbit(int x){
	return x&(-x);
}

void update(int x,int val){
	while(x <= n){
		sum[x] += val;
		x += lowbit(x);
	}
}
int query(int x){
	int s=0;
	while(x>0){
		s += sum[x];
		x -= lowbit(x);
	}
	return s;
}
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		index[i]=0;
	}
	set<pair<int,int> >S;
	for(int i=1;i<=n;i++){
		S.insert(make_pair(-a[i],i));
	}
	int m;scanf("%d",&m);
	vector<pair<pair<int,int>,int>>Q;
	for(int i=0;i<m;i++){
		int x,y;scanf("%d%d",&x,&y);
		Q.push_back(make_pair(make_pair(x,y),i));
	}
	sort(Q.begin(),Q.end());
	int now = 0;
	for(int i=0;i<Q.size();i++){
		while(now<Q[i].first.first){
			now=now+1;
			pair<int,int> tmp = *S.begin();
			update(tmp.second,1);
			index[tmp.second]=1;
			S.erase(tmp);
		}
		int pos = Q[i].first.second;
		int l=1,r=n,Ans=n;
		while(l<=r){
			int mid=(l+r)/2;
			if(query(mid)>=pos){
				Ans=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		ans[Q[i].second]=a[Ans];
	}
	for(int i=0;i<m;i++){
		cout<<ans[i]<<endl;
	}
}
int main(){
	solve();
}