YPKTH Phần tử thứ K

Cho dãy số A có N phần tử nguyên phân biệt. Cho Q truy vấn, mỗi truy vấn có dạng: L R K

Yêu cầu: mỗi truy vấn xuất ra phần tử lớn thứ K sau khi sắp xếp các phần tử A_L, A_L+1, …, A_R theo thứ tự tăng dần.

Input:

• Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 10⁵)
• Dòng tiếp theo chứa N số nguyên A₁, A₂, …, A_N. (|A_i| ≤ 10⁹ với 1 ≤ i ≤ N)
• Dòng tiếp theo chứa số nguyên dương Q (1 ≤ Q ≤ 10⁵).
• Q dòng tiếp theo, mỗi dòng chứa 3 số L, R, K. (1 ≤ L ≤ R ≤ N; 1 ≤ K ≤ R-L+1)

Output: Q dòng, mỗi dòng chứa câu trả lời cho một truy vấn theo thứ tự nhập vào.

Input	Output
7 2 1 5 4 3 6 8 4 1 2 2 3 7 4 4 6 2 5 5 1	2 6 4 3