Sau khi bị chém thành đôi bởi đòn "World Cutting Slash", hai mảnh thân là Go và Jo bị chia cắt và lạc ở hai vị trí khác nhau.

Cho một bản đồ 2D có ~n~ vị trí, vị trí thứ ~i~ có độ dài là ~a_i~. Cho ~q~ truy vấn, mỗi truy vấn cung cấp vị trí của hai mảnh thân lần lượt là ~l~ và ~r~. Hãy tính tổng quãng đường để hai mảnh thân có thể tìm lại được nhau.

Dữ liệu nhập (Input)

• Dòng đầu gồm một số nguyên dương ~n~ là số vị trí ở tử địa Shinjuku (~1 \le n \le 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~, trong đó ~a_i~ biểu thị độ dài của vị trí thứ ~i~ (~1 \le a_i \le 10^9~).
• Dòng thứ ba gồm một số nguyên ~q~ là số lượng truy vấn (~1 \le q \le 100~).
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~l~ và ~r~ biểu thị vị trí của hai mảnh thân Go và Jo (~1 \le l, r \le n~).

Lưu ý: ~l~ phải nhỏ hơn ~r~.

Dữ liệu xuất (Output)

• Gồm ~q~ dòng, mỗi dòng là một số nguyên duy nhất biểu thị tổng quãng đường tìm thấy nhau của mỗi truy vấn.

Sample Input 1

5
10 20 30 40 50
1
1 2

Sample Output 1

30