다음과 같은 함수가 있다.</p>

• f(1, j) = a[j], 1 ≤ j ≤ n
• f(i, j) = min(f(i-1, j), f(i-1, j-1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n

여기서 a는 길이가 n인 배열이다.

배열 a의 값과 쿼리 x_i, y_i가 주어졌을 때, f(x_i, y_i)값을 출력하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 배열 a의 크기 n (1 ≤ n ≤ 10⁵)가 주어지고, 둘째 줄에 배열 a[1], a[2], ..., a[n]이 주어진다. (0 ≤ a[i] ≤ 10⁴)</p>

다음  줄에는 쿼리의 개수 m (1 ≤ m ≤ 10⁵)가 주어지고, 다음 m개의 줄에는 쿼리 x_i, y_i가 주어진다. (1 ≤ x_i ≤ y_i ≤ n)

출력 형식

각각의 쿼리마다 f(x_i, y_i)를 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

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

예제 출력 1

12
9
9
5

예제 입력 2

7
1 3 2 3 4 0 2
4
4 5
2 3
1 4
4 6

예제 출력 2

11
4
3
0