시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 100 20 13 39.394%

문제

다음과 같은 함수가 있다.

  • 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의 값과 쿼리 xi, yi가 주어졌을 때, f(xi, yi)값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 배열 a의 크기 n (1 ≤ n ≤ 105)가 주어지고, 둘째 줄에 배열 a[1], a[2], ..., a[n]이 주어진다. (0 ≤ a[i] ≤ 104)

다음  줄에는 쿼리의 개수 m (1 ≤ m ≤ 105)가 주어지고, 다음 m개의 줄에는 쿼리 xi, yi가 주어진다. (1 ≤ xi ≤ yi ≤ n)

출력

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

예제 입력 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

출처