Có \(N\) que diêm được đánh số từ \(0\) đến \(N-1\). Que diêm thứ \(i\) sẽ thời gian cháy hết là \(b_i\). Nếu thắp sáng cả \(2\) đầu que diêm thì thời gian cháy sẽ giảm phân nửa

Sắp xếp

• Buộc phần sau của tất cả các que diêm lại với nhau tại một điểm và phần đầu được giữ tự do. (Phần thân không chạm nhau)

Yêu cầu

• Có \(Q\) truy vấn. Mỗi truy vấn sẽ trả lời: Nếu đốt đầu tự do của tất cả các que diêm được đánh số từ \(L\) đến \(R\) thì cần bao nhiêu thời gian để cháy hết tất cả.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(N\) \((1 \le N \le 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(b_i\) là thời gian cháy hết que diêm thứ \(i\) \((1 \le b_i \le 10^8)\)
• Dòng thứ 3 chứa số nguyên \(Q\) \((1 \le Q \le 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) \((0 \le L \le R \le N-1)\)

Dữ liệu ra

• In ra đáp án của mỗi câu truy vấn

Input 1

2
3 5
1
0 1

Output 1

4.0

Input 2

18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
1
4 10

Output 2

9.0

Giải thích 2

Đốt que diêm từ vị trí 4 đến 10. Thì thời gian cháy hết các que diêm như sau: 8.0, 9.0, 7.0, 6.0, 5.0, 6.0, 7.0, 6.0, 7.5, 5.0, 8.5, 8.0, 6.0, 6.0, 7.0, 6.0, 8.0, 7.0. Vậy thời gian cháy hết là 9.0