14181번 - 함수와 쿼리

문제

다음과 같은 함수가 있다.

• 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⁴)

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

출력

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

제한

힌트