#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = 100;
int stepTo[N], leftMin[N], DEC[N], a[N];
long long sum[N];
inline long long calc(int take, int L, int R) {
  return sum[R] - sum[L - 1] + a[L] * (take - (R - L + 1));
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
  a[0] = -1;
  leftMin[1] = 0;
  DEC[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] < a[i - 1])
      DEC[i] = i;
    else
      DEC[i] = DEC[i - 1];
    int t = i - 1;
    while (a[t] >= a[i]) t = leftMin[t];
    leftMin[i] = t;
  }
  for (int i = 1; i <= n; i++) stepTo[i] = min(DEC[i], leftMin[i]);
  int m;
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    int pos = b;
    long long ret = 1e16;
    while (1) {
      ret = min(ret, calc(a, pos, b));
      if (b - pos + 1 == a)
        break;
      else {
        pos = stepTo[pos];
        pos = max(pos, b - a + 1);
      }
    }
    printf("%I64d\n", ret);
  }
  return 0;
}
