This is the harder version of the problem. In this version, 1 ≤ n, m ≤ 2⋅10^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,...,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 ≤ 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=[b_1, b_2, ..., b_k] is lexicographically smaller than the sequence c=[c_1, c_2, ..., 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 ≤ t ≤ k) such that b_1=c_1, b_2=c_2, ..., b_{t-1}=c_{t-1} and at the same time b_t<c_t. 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=[a_1,a_2,...,a_n] and m requests, each consisting of two numbers k_j and pos_j (1 ≤ k ≤ n, 1 ≤ pos_j ≤ k_j). For each query, print the value that is in the index pos_j of the optimal subsequence of the given sequence a for k=k_j.

For example, if n=4, a=[10,20,30,20], k_j=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 k_j=2, pos_j=1 is the number 20, and the answer to the request k_j=2, pos_j=2 is the number 30.

Input

The first line contains an integer n (1 ≤ n ≤ 2⋅10^5) — the length of the sequence a.

The second line contains elements of the sequence a: integer numbers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

The third line contains an integer m (1 ≤ m ≤ 2⋅10^5) — the number of requests.

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

Output

Print m integers r_1, r_2, ..., r_m (1 ≤ r_j ≤ 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.

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

Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
from bisect import bisect_left, bisect_right, insort_right

class SquareSkipList:

	def __init__(self, values=None, sorted_=False, square=1000, seed=42):
		inf = float('inf')
		self.square = square
		if values is None:
			self.rand_y = seed
			self.layer1 = [inf]
			self.layer0 = [[]]
		else:
			self.layer1 = layer1 = []
			self.layer0 = layer0 = []
			if not sorted_:
				values.sort()
			y = seed
			l0 = []
			for v in values:
				y ^= (y & 524287) << 13
				y ^= y >> 17
				y ^= (y & 134217727) << 5
				if y % square == 0:
					layer0.append(l0)
					l0 = []
					layer1.append(v)
				else:
					l0.append(v)
			layer1.append(inf)
			layer0.append(l0)
			self.rand_y = y

	def add(self, x):
		y = self.rand_y
		y ^= (y & 524287) << 13
		y ^= y >> 17
		y ^= (y & 134217727) << 5
		self.rand_y = y
		if y % self.square == 0:
			(layer1, layer0) = (self.layer1, self.layer0)
			idx1 = bisect_right(layer1, x)
			layer1.insert(idx1, x)
			layer0_idx1 = layer0[idx1]
			idx0 = bisect_right(layer0_idx1, x)
			layer0.insert(idx1 + 1, layer0_idx1[idx0:])
			del layer0_idx1[idx0:]
		else:
			idx1 = bisect_right(self.layer1, x)
			insort_right(self.layer0[idx1], x)

	def remove(self, x):
		idx1 = bisect_left(self.layer1, x)
		layer0_idx1 = self.layer0[idx1]
		idx0 = bisect_left(layer0_idx1, x)
		if idx0 == len(layer0_idx1):
			del self.layer1[idx1]
			self.layer0[idx1] += self.layer0.pop(idx1 + 1)
		else:
			del layer0_idx1[idx0]

	def search_higher_equal(self, x):
		idx1 = bisect_left(self.layer1, x)
		layer0_idx1 = self.layer0[idx1]
		idx0 = bisect_left(layer0_idx1, x)
		if idx0 == len(layer0_idx1):
			return self.layer1[idx1]
		return layer0_idx1[idx0]

	def search_higher(self, x):
		idx1 = bisect_right(self.layer1, x)
		layer0_idx1 = self.layer0[idx1]
		idx0 = bisect_right(layer0_idx1, x)
		if idx0 == len(layer0_idx1):
			return self.layer1[idx1]
		return layer0_idx1[idx0]

	def search_lower(self, x):
		idx1 = bisect_left(self.layer1, x)
		layer0_idx1 = self.layer0[idx1]
		idx0 = bisect_left(layer0_idx1, x)
		if idx0 == 0:
			return self.layer1[idx1 - 1]
		return layer0_idx1[idx0 - 1]

	def pop(self, idx):
		layer0 = self.layer0
		s = -1
		for (i, l0) in enumerate(layer0):
			s += len(l0) + 1
			if s >= idx:
				break
		if s == idx:
			layer0[i] += layer0.pop(i + 1)
			return self.layer1.pop(i)
		else:
			return layer0[i].pop(idx - s)

	def __getitem__(self, item):
		layer0 = self.layer0
		s = -1
		for (i, l0) in enumerate(layer0):
			s += len(l0) + 1
			if s >= item:
				break
		if s == item:
			return self.layer1[i]
		else:
			return layer0[i][item - s]

	def print(self):
		print(self.layer1)
		print(self.layer0)
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
M = int(input())
Ans = [-1] * M
KP = [list(map(int, input().split())) for _ in range(M)]
Idx_query = list(range(M))
Idx_query.sort(key=lambda x: KP[x][0])
Idx = list(range(N))
Idx.sort(key=lambda x: A[x], reverse=True)
n = 0
st = SquareSkipList()
for idx_query in Idx_query:
	(k, pos) = KP[idx_query]
	while n < k:
		idx = Idx[n]
		st.add(idx)
		n += 1
	Ans[idx_query] = A[st[pos - 1]]
print('\n'.join(map(str, Ans)))


class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def _sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, val):
		i = i + 1
		while i <= self.n:
			self.bit[i] += val
			i += i & -i

	def get_sum(self, l, r):
		return self._sum(r) - self._sum(l)

	def bisect_left(self, val):
		sum_ = 0
		pos = 0
		bit_length = (n + 1).bit_length()
		for i in range(bit_length, -1, -1):
			k = pos + (1 << i)
			if k < self.n + 1 and sum_ + self.bit[k] < val:
				sum_ += self.bit[k]
				pos += 1 << i
		return pos + 1
from operator import itemgetter
n = int(input())
a = list(map(int, input().split()))
m = int(input())
info = [list(map(int, input().split())) + [i] for i in range(m)]
b = list(zip(a, range(len(a))))
b = sorted(b, key=itemgetter(0), reverse=True)
info = sorted(info, key=itemgetter(0))
bit = BIT(n)
ans = [0] * m
cnt = 0
for i in range(m):
	(k, pos, ind) = info[i]
	while cnt < k:
		bit.add(b[cnt][1], 1)
		cnt += 1
	ans[ind] = a[bit.bisect_left(pos) - 1]
for i in ans:
	print(i)


import sys
input = sys.stdin.readline
from operator import itemgetter

def updatebit(BITTree, n, i, v):
	while i <= n:
		BITTree[i] += v
		i += i & -i

def bisect_left(val):
	sum_ = 0
	pos = 0
	bit_length = (n + 1).bit_length()
	for i in range(bit_length, -1, -1):
		k = pos + (1 << i)
		if k < n + 1 and sum_ + l[k] < val:
			sum_ += l[k]
			pos += 1 << i
	return pos
n = int(input())
l = [0] * (n + 1)
a = [int(i) for i in input().split() if i != '\n']
empty = []
for i in range(len(a)):
	empty.append([a[i], i + 1])
empty.sort(key=lambda x: x[1])
empty.sort(key=lambda x: x[0], reverse=True)
m = int(input())
info = [list(map(int, input().split())) + [i] for i in range(m) if i != '\n']
info = sorted(info, key=itemgetter(0))
(bit, ans, cnt) = ([0] * (n + 1), [0] * m, 0)
for i in range(m):
	(k, pos, ind) = info[i]
	while cnt < k:
		updatebit(l, n, empty[cnt][1], 1)
		cnt += 1
	ans[ind] = a[bisect_left(pos)]
for i in ans:
	sys.stdout.write(str(i) + '\n')