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ử nhỏ thứ \(k\) sau khi sắp xếp các phần tử \(a_l, a_{l+1}, \dots, a_r\) theo thứ tự tăng dần.

Input

• Dòng đầu tiên chứa số \(n\) (\(1 \le n \le 10^5\)).
• Dòng tiếp theo chứa \(n\) số nguyên phân biệt \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).
• Dòng tiếp theo chứa số \(q\) (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(l, r, k\) (\(1 \le l \le r \le n, 1 \le k \le r - l + 1\)).

Output

• Gồm \(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.

Example

7
1 5 2 6 3 7 4
3
2 5 3
4 4 1
1 7 3

5
6
3