Dãy Con Tối Ưu

Cho dãy số nguyên $a=[a_1,a_2,\dots ,a_n]$ có độ dài $n$.

Một dãy con của $a$ là dãy thu được bằng cách xóa đi $0$ hoặc nhiều phần tử của $a$ (không cần liên tiếp).

Với một số nguyên dương $k$ ($1\le k\le n$), dãy con của $a$ được gọi là tối ưu nếu:

1. Nó có đúng $k$ phần tử và tổng các phần tử lớn nhất có thể trong số mọi dãy con độ dài $k$.
2. Trong số mọi dãy con thỏa mãn điều kiện trên, nó có thứ tự từ điển nhỏ nhất.

Bạn được cho $m$ truy vấn, mỗi truy vấn gồm hai số nguyên $k_j$ và $po{s}_j$ ($1\le po{s}_j\le k_j\le n$). Với mỗi truy vấn, hãy in ra giá trị tại vị trí $po{s}_j$ của dãy con tối ưu của $a$ ứng với $k=k_j$.

Ví dụ với $a=[10,20,30,20]$ và $k=2$, dãy con tối ưu là $[20,30]$ (giá trị $20$ là phần tử thứ hai của $a$ — vị trí nhỏ hơn so với $20$ ở cuối). Vậy với $k_j=2$, $po{s}_j=1$ thì đáp án là $20$, và với $po{s}_j=2$ thì đáp án là $30$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa số nguyên $m$ — số truy vấn.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $k_j$ và $po{s}_j$.

Dữ liệu ra

In ra $m$ dòng, mỗi dòng chứa đáp án cho truy vấn tương ứng.

Ràng buộc

• $1\le n,m\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• $1\le po{s}_j\le k_j\le n$

Ví dụ