Cho dãy a1, a2, …, an và q truy vấn như sau:

• K S: đưa ra giá trị nhỏ thứ K.
• K L: đưa ra giá trị lớn thứ K.

Dữ liệu: vào từ file văn bản ABD.INP

• Dòng 1: Số nguyên dương N (0 ≤ N ≤ 10^6)
• Dòng 2: N số nguyên dương a1, a2, …, an (1 ≤ ai ≤ 10^9)
• Dòng 3: Số nguyên dương Q (1 ≤ Q ≤ 10^6)
• Q dòng tiếp theo chứa các truy vấn dạng K S hoặc K L (1 ≤ K ≤ 10^5)

Kết quả: ghi ra file văn bản ABD.OUT, trên từng dòng, mỗi dòng là kết quả ứng với một truy vấn.

Ví dụ:

ABD.INP

5
1 2 3 4 5
3
3 L
3 S
1 L

ABD.OUT

3
3
5