Dãy con tối ưu (bản dễ)

Cho một dãy số nguyên $a=[a_1,a_2,\dots ,a_n]$ độ dài $n$. Một dãy con của $a$ thu được bằng cách xóa đi không hoặc nhiều phần tử (các phần tử còn lại không nhất thiết đứng liền nhau, nhưng giữ nguyên thứ tự ban đầu).

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

• nó có độ dài đúng bằng $k$ và tổng các phần tử là lớn nhất có thể trong số mọi dãy con độ dài $k$;
• trong số mọi dãy con độ dài $k$ đạt tổng lớn nhất, nó là dãy có thứ tự từ điển nhỏ nhất.

Nhắc lại: dãy $b=[b_1,\dots ,b_k]$ nhỏ hơn theo thứ tự từ điển so với dãy $c=[c_1,\dots ,c_k]$ nếu tồn tại vị trí $t$ sao cho $b_1=c_1,\dots ,b_{t-1}=c_{t-1}$ và $b_t<c_t$.

Cho $m$ truy vấn, mỗi truy vấn gồm hai số $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ị nằm ở vị trí $po{s}_j$ (đánh số từ 1) của dãy con tối ưu ứng với $k=k_j$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, độ dài của dãy $a$.
• 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$ số nguyên, mỗi số trên một dòng: đáp án cho các truy vấn theo đúng thứ tự chúng xuất hiện.

Ràng buộc

• $1\le n\le 100$
• $1\le a_i\le {10}^9$
• $1\le m\le 100$
• $1\le po{s}_j\le k_j\le n$

Ví dụ