4호선은 매우 신기한 노선이다.

4호선은 다른 노선과 다르게 기존 노선에서 안산선 및 과천선이 추가된 식이기 때문에 남태령-선바위 구간에서 통행방식 입체 교차 를 한다.

그리고 직류전용전동차는 사당-당고개 , 그외의 직/교류 전동차는 안산-당고개 오이도- 당고개 구간을 왕복한다. 우리는 주어진 각 역의 가장 짧은 거리를 구하면 된다. 4호선은 단일 일자형 노선이다.

로그램의 실행 시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력

• 첫줄에는 정거장의 수를 나타내는 N(1≤N≤ 5,000,000) 이 주어지고, N-1개만큼 i번째 역과 i+1번째 역의 거리(1≤거리≤10) 이 주 어진다.
• 그리고 그 다음줄에 테스트 케이스 의 개수 T(1≤T≤5,000,000) 이 주어지고 각 줄에 두 역 a,b가 주어진다. 여기서 항상 a < b이다.

출력

입출력 예

입력

5
1 2 3 4
2
1 3
2 3

출력 

3
2

출처:conankun