Tại phòng nghiên cứu năng lượng, các nhà khoa học ở đây chủ yếu nghiên cứu về tối ưu hóa. Với bài toán đang nghiên cứu hiện tại, có ~n~ thuật toán dùng để xử lý bài toán đó, thuật toán thứ ~i~ có độ tốt là ~a_i~ và giá trị này là một số nguyên.

Các nhà khoa học muốn kết hợp hai thuật toán khác nhau để tạo ra thuật toán tốt nhất. Sau khi kết hợp hai thuật toán ~i~ và ~j~, thuật toán mới sẽ có độ tốt là ~a_i \times a_j~. Đồng thời, để nghiên cứu sâu hơn, các nhà khoa học muốn biết trong các thuật toán đánh số từ ~L~ đến ~R~, có thể tạo ra thuật toán có giá trị tốt nhất là bao nhiêu?

Yêu cầu: Với mỗi câu hỏi gồm hai số ~L, R~, hãy xác định giá trị tốt nhất có thể tạo được khi chỉ sử dụng các thuật toán đánh số từ ~L~ đến ~R~.

Input

• Dòng đầu tiên gồm số ~n~ tức số thuật toán.
• Dòng sau gồm ~n~ phần tử ~a_i~ tức độ tốt của các thuật toán.
• Dòng tiếp theo gồm số ~q~, tức số câu hỏi.
• ~q~ dòng sau, mỗi dòng gồm hai số ~L, R~ (~L < R~).

Output

• Với mỗi câu hỏi, in ra đáp án trên các dòng tương ứng.

Sample Input 1

4 
1 -2 3 -4 
4 
1 2 
1 3 
3 4 
1 4 

Sample Output 1

8