Hạo mới mở một tiệm bánh ngọt siêu to khổng lồ. Ngày đầu tiên khai trương, có \(n\) người quen đến xếp hàng ủng hộ Hạo, người thứ \(i\) mang theo một số tiền là \(a_i\) đồng. Cầm trên tay bản danh sách khách hàng, Hạo chợt nảy ra một câu hỏi trong đầu: Nếu như chỉ bán bánh cho các vị khách từ vị trí \(l\) tới vị trí \(r\), thì nên để giá bánh là bao nhiêu để thu được lợi nhuận lớn nhất?

Do mới mở hàng nên Hạo chưa có kinh nghiệm ra giá, cậu không biết nên bán bánh với giá bao nhiêu tiền. Biết rằng, mỗi vị khách đến cửa hàng đều mong muốn mua bánh hết số tiền họ mang theo, và Hạo cũng muốn thu được tiền nhiều nhất có thể. Vì vậy, cậu cần tìm một giá tiền lớn nhất để bán bánh, từ đó thu được lợi nhuận lớn nhất.

Yêu cầu

• Giúp Hạo chọn giá tiền lớn nhất có thể cho những chiếc bánh sao cho khi bán hàng, các khách mua đều không bị thừa hay thiếu tiền?

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(n\) - số lượng khách hàng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ... a_n\) phân tách nhau bởi dấu cách - lượng tiền mà mỗi khách hàng mang theo.
• Dòng thứ ba chứa số nguyên dương \(m\) - số câu hỏi mà Hạo tự đặt ra.
• Trên \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(l_i, r_i\) thể hiện một câu hỏi mà Hạo tự đặt ra.

Dữ liệu ra

• Trên \(m\) dòng, mỗi dòng đưa ra giá bánh mà Hạo sẽ lựa chọn cho trường hợp tương ứng.

Ràng buộc

• \(1 \le n \le 10^5\)
• \(1 \le a_i \le 10^9\)
• \(1 \le m \le 10^6\)

Input 1

8
7 2 3 5 10 3 12 18
3
1 3
6 8
4 5

Output 1

1
3
5