#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 1000;
const long long inf = 1e18;
long long n, a[maxn], m, s[maxn];
long long Y(long long x) { return s[x] - x * a[x]; }
long long X(long long x) { return a[x]; }
long double slope(long long x, long long y) {
  long long ggg = 1;
  if (a[x] == a[y]) {
    if (Y(y) > Y(x))
      return inf;
    else
      return -inf;
  }
  return (long double)((s[x] - x * a[x]) - (s[y] - y * a[y])) / (a[x] - a[y]);
}
long long dp_val(long long l, long long r, long long loc) {
  return s[r] - s[loc] + (l - r + loc) * a[loc];
}
struct convex {
  vector<long long> q;
  long long hd, tl;
  void init(long long sz) {
    q.resize(sz);
    hd = 0, tl = -1;
  }
  void insert(long long u) {
    long double g1, g2;
    if (hd < tl) g1 = slope(q[tl] - 1, q[tl]), g2 = slope(q[tl], u);
    while (hd < tl && slope(q[tl - 1], q[tl]) < slope(q[tl], u)) {
      tl--;
      if (hd < tl) g1 = slope(q[tl] - 1, q[tl]), g2 = slope(q[tl], u);
      long long jk = 1;
    }
    q[++tl] = u;
  }
  long long query(long long l, long long r) {
    if (hd == tl) return dp_val(l, r, q[hd]);
    long long gl = hd, gr = tl - 1;
    while (gl < gr) {
      long long mid = (gl + gr) >> 1;
      if (l - r > slope(q[mid], q[mid + 1]))
        gr = mid;
      else
        gl = mid + 1;
    }
    long long ans = q[gl];
    long double ggg = slope(q[gl], q[tl]);
    if (l - r <= slope(q[gl], q[tl])) ans = q[tl];
    return dp_val(l, r, ans);
  }
};
bool cmp(long long x, long long y) { return a[x] < a[y]; }
struct segment_tree {
  convex ori[maxn << 2];
  void build(long long l, long long r, long long rt) {
    ori[rt].init(r - l + 1);
    vector<long long> tmp;
    for (long long i = (l), iend = (r); i <= iend; i++) tmp.push_back(i);
    sort(tmp.begin(), tmp.end(), cmp);
    for (long long i = (0), iend = (tmp.size() - 1); i <= iend; i++) {
      ori[rt].insert(tmp[i]);
    }
    if (l == r) return;
    long long mid = (l + r) >> 1;
    build(l, mid, (rt << 1));
    build(mid + 1, r, (rt << 1 | 1));
  }
  long long query(long long l, long long r, long long rt, long long tl,
                  long long tr, pair<long long, long long> val) {
    if (tl <= l && r <= tr) {
      return ori[rt].query(val.first, val.second);
    }
    long long mid = (l + r) >> 1;
    long long ans = 1e18;
    if (tl <= mid) ans = min(ans, 1ll * query(l, mid, (rt << 1), tl, tr, val));
    if (tr >= mid + 1)
      ans = min(ans, 1ll * query(mid + 1, r, (rt << 1 | 1), tl, tr, val));
    return ans;
  }
} t;
signed main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (long long i = (1), iend = (n); i <= iend; i++)
    cin >> a[i], s[i] = s[i - 1] + a[i];
  t.build(1, n, 1);
  long long m;
  cin >> m;
  for (long long i = (1), iend = (m); i <= iend; i++) {
    long long l, r;
    cin >> l >> r;
    cout << t.query(1, n, 1, r - l + 1, r, make_pair(l, r)) << endl;
  }
  return 0;
}
