함수와 쿼리

길이가 $n$인 배열 $a = (a_1, a_2, \dots, a_n)$이 있다. 함수 $f$를 다음과 같이 정의한다.

$f(1,\, j) = a_j \qquad (1 \le j \le n)$

$f(i,\, j) = \min(f(i-1,\, j),\ f(i-1,\, j-1)) + a_j \qquad (2 \le i \le n,\ i \le j \le n)$

배열 $a$와 쿼리 $m$개가 주어진다. 각 쿼리는 두 정수 $x_i$, $y_i$로 이루어지고 $f(x_i, y_i)$의 값을 묻는다. 모든 쿼리의 답을 구하는 프로그램을 작성하시오.

첫째 줄에 배열 $a$의 크기 $n$ ($1 \le n \le 10^5$)이 주어진다.

둘째 줄에 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다. ($0 \le a_j \le 10^4$)

셋째 줄에 쿼리의 개수 $m$ ($1 \le m \le 10^5$)이 주어진다. 이어지는 $m$개의 줄에 쿼리가 한 줄에 하나씩 $x_i$, $y_i$ 순서로 주어진다. ($1 \le x_i \le y_i \le n$)

쿼리가 주어진 순서대로 $f(x_i, y_i)$의 값을 한 줄에 하나씩 출력한다.