Một công ty xây dựng nọ đang lên kế hoạch cho việc sửa chữa một con đường cao tốc có chiều dài là \(n\) kilomet. Con đường này được đánh số từ \(1\) đến \(n+1\) tại những vị trí cách đều nhau đúng \(1\) kilomet, bắt đầu từ vị trí đầu của con đường. Chi phí sửa chữa cho đoạn \(1\) kilomet từ vị trí \(i\) đến \(i+1\) là \(A_i\) với \(1 \le i \le n\).

Một kiến trúc sư người Ý đảm nhiệm vai trò này và đang khảo sát mức độ hư hại cũng như chi phí để sửa chữa con đường này. Do kinh phí thời điểm hiện tại không đủ để thi công một lúc cả con đường. Anh ấy kế hoạch tính toán để chọn ra đoạn đường phù hợp nhất để sửa chữa đầu tiên. Anh ấy khảo sát con đường bằng cách chọn ra một đoạn từ vị trí \(L\) đến vị trí \(R\) trên con đường và tính xem chi phí sửa chữa trung bình trên \(1\) kilomet của đoạn này là bao nhiêu.

Yêu cầu: Cho \(Q\) câu truy vấn \((L, R)\). Hãy tính chi phí sửa chữa trung bình trên \(1\) kilomet của vị trí \(L\) đến vị trí \(R\).

Input

• Dòng đầu tiên gồm số \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).
• Dòng thứ ba là số \(Q\) – số lượng câu truy vấn.
• Q dòng tiếp theo, mỗi dòng gồm 2 số \(L\) và \(R (L<R)\).

Output

• Gồm \(Q\) dòng tương ứng là kết quả của câu truy vấn thứ \(i\), kết quả được làm tròn đến chữ số thập phân thứ \(6\).

Scoring

• \(0 \le A_i \le 10^9\)
• Subtask \(1\) (\(70\%\) số điểm): \(1 \le q,n \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le q,n \le 5*10^4\).

Example

5
1 2 3 4 5
3
1 4
2 5
4 6

2.000000
3.000000
4.500000