#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
pair<int, int> Q[100000 + 5];
int tp;
int size, n, m, a[100000 + 5], Ans[100000 + 5], s[100000 + 5],
    block[100000 + 5], num = 0, q[100000 + 5], top, b[100000 + 5],
                       id[100000 + 5];
struct ques {
  int r, t, id;
};
vector<ques> v[350][350];
double Calc(pair<int, int> x, pair<int, int> y) {
  return (double)(y.second - x.second) / (x.first - y.first);
}
int Calc(int x, int t, int r) { return s[r] - s[x] + a[x] * (t - (r - x)); }
void Add(int ID, int a, int b) {
  while (tp > 1 && Calc(Q[tp - 1], Q[tp]) >= Calc(Q[tp], make_pair(a, b))) --tp;
  id[++tp] = ID;
  Q[tp] = make_pair(a, b);
}
int Bl(int r, int t) {
  int l = r - t + 1, res = 2e9;
  for (int i = r; i >= l; --i) res = min(res, Calc(i, t, r));
  return res;
}
int Solve(int x) {
  int l = 1, r = tp, res = 2e9;
  while (l <= r) {
    int mid = l + r >> 1;
    double pt;
    res = min(res, x * Q[mid].first + Q[mid].second);
    pt = (mid == 1 ? -1e9 : Calc(Q[mid - 1], Q[mid]));
    if (pt <= x)
      l = mid + 1;
    else
      r = mid - 1;
  }
  for (int i = 0; i <= 5; ++i)
    if (l + i <= tp) res = min(res, x * Q[l + i].first + Q[l + i].second);
  return res;
}
int main() {
  n = read();
  size = sqrt(n);
  for (int i = 1; i <= n; ++i)
    a[i] = read(), s[i] = s[i - 1] + a[i], block[i] = (i - 1) / size + 1;
  m = read();
  num = block[n];
  for (int i = 1; i <= m; ++i) {
    int t = read(), r = read();
    if (block[r - t + 1] + 1 >= block[r]) {
      Ans[i] = Bl(r, t);
      continue;
    }
    int b1 = block[r - t + 1] + 1, b2 = block[r] - 1;
    v[b1][b2].push_back((ques){r, t, i});
  }
  for (int i = 1; i <= num; ++i) {
    top = tp = 0;
    int now = 1e9;
    for (int j = i; j; --j) {
      int l = (j - 1) * size + 1, r = min(n, j * size);
      for (int k = r; k >= l; --k)
        if (a[k] < now) {
          Add(k, a[k], a[k] * k - s[k]);
          now = a[k];
        }
      for (int k = 0; k < v[j][i].size(); ++k) {
        Ans[v[j][i][k].id] =
            Solve(v[j][i][k].t - v[j][i][k].r) + s[v[j][i][k].r];
        for (int p = v[j][i][k].r; p > i * size; --p)
          Ans[v[j][i][k].id] =
              min(Ans[v[j][i][k].id], Calc(p, v[j][i][k].t, v[j][i][k].r));
        for (int p = (j - 1) * size; p >= v[j][i][k].r - v[j][i][k].t + 1; --p)
          Ans[v[j][i][k].id] =
              min(Ans[v[j][i][k].id], Calc(p, v[j][i][k].t, v[j][i][k].r));
      }
    }
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", Ans[i]);
  return 0;
}
