Cho dãy số \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\). Có \(M\) câu hỏi, mỗi câu hỏi gồm hai số nguyên \(L\) và \(R\). Với mỗi câu hỏi, hãy tìm giá trị lớn nhất của các phần tử trong đoạn từ \(L\) đến \(R\) của dãy \(A\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).
• Dòng thứ ba chứa số nguyên dương \(M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\) đại diện cho một câu hỏi.

Output

• Ghi ra \(M\) dòng, mỗi dòng là giá trị lớn nhất trong đoạn \([L_i, R_i]\) tương ứng.

Example

5
34 23 12 34 2 
3
1 3
2 4
5 5

34
34
2

Constraints

• \(1 \le N, M \le 5 \cdot 10^5\)
• \(1 \le A_i \le 10^9\)
• \(1 \le L_i \le R_i \le N\)