연결된 그릇

존은 학교에서 물리 연습 문제를 풀고 있다. 오늘은 연통관의 법칙을 공부하고 있다. 이 법칙에 따르면, 같은 액체가 들어 있는 연결된 용기들에서 액체가 안정되면 모양과 부피에 관계없이 모든 용기의 액면 높이가 같아진다.

실험실에는 존이 밑면적이 1제곱데시미터이고 높이가 무한대로 간주되는 원기둥 모양 용기 $n$개를 가지고 있다. 용기는 1번부터 $n$번까지 번호가 매겨져 있다. 용기 $i$와 $i+1$은 높이가 $h_i$데시미터인 아주 얇은 다리로 연결되어 있다. 모든 높이는 서로 다르다.

연습 과제에는 서로 독립적인 $t$개의 실험이 있다. 각 실험을 시작할 때 모든 용기는 비어 있다. $i$번째 실험에서는 용기 $a_i$에 물을 천천히 붓고, 용기 $b_i$에 물이 조금이라도 나타나면 실험을 끝낸다. 실험 결과는 용기 $a_i$에 부은 물의 총량을 리터 단위로 나타낸 값이다(세제곱데시미터와 같다).

연통관의 법칙은 용기 $i$와 $i+1$의 수위가 둘 다 $h_i$ 이상일 때에만 적용된다. 그 전에 한쪽 용기의 수위만 $h_i$에 도달하면 그 수위는 그대로 유지되고, 그 용기로 들어오는 남는 물은 다리를 지나 다른 용기로 흘러간다.

존이 결과를 확인하도록 도와라.

첫 번째 줄에 용기의 개수 $n$이 주어진다($2 \le n \le 2 \cdot 10^5$).

두 번째 줄에는 다리의 높이 $h_1, h_2, \ldots, h_{n-1}$이 데시미터 단위로 $n-1$개의 정수로 주어진다($1 \le h_i \le 10^9$). 모든 높이는 서로 다르다.

세 번째 줄에는 실험의 개수 $t$가 주어진다($1 \le t \le 2 \cdot 10^5$).

이어지는 $t$개의 줄에는 $i$번째 실험의 시작 용기 번호 $a_i$와 목표 용기 번호 $b_i$가 주어진다($1 \le a_i \le n$; $1 \le b_i \le n$; $a_i \ne b_i$).

각 실험에 대해 입력 순서대로, 필요한 물의 양을 리터 단위의 정수 하나로 출력한다.