#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10;
const long long INF = 1e15 + 10;
struct node {
  vector<pair<long long, long long> > m;
};
node segt[4 * MAXN];
long long a[MAXN];
long long partial[MAXN];
long long pre_min(long long l, long long r) {
  long long e = r;
  while (e >= l && a[e] >= a[r]) {
    e--;
  }
  return e;
}
long long f(long long l, long long r, long long k) {
  return partial[r] - partial[l - 1] + (k - r + l - 1) * a[l];
}
void build(long long id, long long l, long long r) {
  if (l == r) {
    segt[id].m.push_back(make_pair(1, l));
    return;
  }
  long long mid = (l + r) / 2;
  build(2 * id + 1, l, mid);
  build(2 * id + 2, mid + 1, r);
  long long e = pre_min(l, r);
  segt[id].m.push_back(make_pair(1, r));
  while (e >= l) {
    long long p = segt[id].m.back().second;
    long long z =
        max(r - e + 1, ((partial[p - 1] - partial[e - 1] +
                         (r + 1) * (a[p] - a[e]) - (p * a[p]) + (e * a[e])) /
                        (a[p] - a[e])) +
                           1);
    if (segt[id].m.back().first > z) {
      segt[id].m.pop_back();
      continue;
    }
    segt[id].m.push_back(make_pair(z, e));
    e = pre_min(l, e);
  }
}
long long get_res(long long id, long long L, long long R, long long r,
                  long long k) {
  if (L > r || r > R) {
    return INF;
  }
  if (R == r) {
    long long e =
        (upper_bound(segt[id].m.begin(), segt[id].m.end(), make_pair(k, INF)) -
         1)
            ->second;
    return f(e, R, k);
  }
  long long mid = (L + R) / 2;
  if (r <= mid) {
    return get_res(2 * id + 1, L, mid, r, k);
  }
  return min(get_res(2 * id + 2, mid + 1, R, r, k),
             (k > (r - mid) ? get_res(2 * id + 1, L, mid, mid, k - r + mid) +
                                  partial[r] - partial[mid]
                            : INF));
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
    partial[i] = partial[i - 1] + a[i];
  }
  build(0, 1, n);
  long long q;
  cin >> q;
  for (long long i = 0; i < q; i++) {
    long long x, y;
    cin >> x >> y;
    cout << get_res(0, 1, n, y, x) << endl;
  }
}
