Cho một dãy số nguyên dương \(a_1,a_2,...,a_n\) gồm \(n\) phần tử. Bạn sẽ phải trả lời \(q\) truy vấn, mỗi truy vấn trả lời số trung vị của đoạn \([A_L;A_R]\) \((1 \le L \le R \le n)\).

Định nghĩa: Số trung vị của 1 dãy số là số nằm ở vị trí thứ \(\frac{n}{2} + 1\) sau khi sắp xếp dãy đó tăng dần (với \(n\) lẻ) hoặc ở vị trí thứ \(\frac{n}{2}\) (nếu \(n\) chẵn).

Input

• Dòng đầu chứa số nguyên dương \(n\) không quá \(10^5\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((a_i \le 10^5)\)
• Dòng thứ ba chứa số nguyên dương \(q\) không quá \(1000\) - số truy vấn cần trả lời.
• \(q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(L, R\) \((1 \le L \le R \le n)\)

Output

• Ứng với mỗi truy vấn, in ra kết quả thỏa mãn đề bài.

Example

6
7 9 1 7 8 2
3
1 3
3 6
1 1

7
2
7