DUTUYEN

Cho dãy số X có N phần tử nguyên phân biệt.

Cho P 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ử X_L, X_L+1, …, X_R theo thứ tự tăng dần.

Giới hạn:

1 ≤ N, P ≤ 20000

|X_i| ≤ 200000 với 1 ≤ i ≤ N

1 ≤ L ≤ R ≤ N

1 ≤ K ≤ R-L+1

Input

-       Dòng đầu tiên chứa số N.

-       Dòng tiếp theo chứa N số X₁,X₂, …,X_N.

-       Dòng tiếp theo chứa số P.

-       P dòng tiếp theo, mỗi dòng chứa 3 số L, R, K.

Output

P 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

Input:
6
2 1 5 4 3 6 
2
1 2 2
4 6 2
Output:
2

4