#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], n, sum[N];
long double intx(int k1, int b1, int k2, int b2) {
  return (b1 - b2) / (long double)(k2 - k1);
}
struct CH {
  vector<int> k, b;
  int len;
  inline int y(int id, int x) { return k[id] * x + b[id]; }
  void add(int kk, int bb) {
    if (len == 1 && k[len - 1] == kk) {
      bb = max(bb, b[len - 1]);
      len = 0;
    }
    if (len < 2) {
      k[len] = kk;
      b[len++] = bb;
      return;
    }
    while (len > 1 && ((k[len - 1] == kk && b[len - 1] > bb) ||
                       (kk != k[len - 1] &&
                        intx(k[len - 2], b[len - 2], k[len - 1], b[len - 1]) >=
                            intx(k[len - 1], b[len - 1], kk, bb))))
      --len;
    while (len && k[len - 1] == kk && b[len - 1] > bb) --len;
    if (len && k[len - 1] == kk && b[len - 1] <= bb) return;
    k[len] = kk;
    b[len++] = bb;
  }
  bool chk(int id, int x) { return y(id, x) >= y(id + 1, x); }
  int get(int x) {
    int l = -1, r = len - 1;
    while (r - l > 1) {
      int mid = (l + r) >> 1;
      if (chk(mid, x))
        l = mid;
      else
        r = mid;
    }
    return y(r, x);
  }
};
void merge(CH &res, CH &a, CH &b) {
  res.len = 0;
  res.k.resize(a.len + b.len);
  res.b.resize(a.len + b.len);
  int l = 0, r = 0;
  while (l + r < a.len + b.len) {
    if (l == a.len)
      res.add(b.k[r], b.b[r]), ++r;
    else if (r == b.len)
      res.add(a.k[l], a.b[l]), ++l;
    else if (a.k[l] > b.k[r])
      res.add(a.k[l], a.b[l]), ++l;
    else
      res.add(b.k[r], b.b[r]), ++r;
  }
}
struct TNode {
  int l, r;
  CH v;
} t[N << 2];
inline int lc(int pos) { return pos << 1; }
inline int rc(int pos) { return pos << 1 | 1; }
inline void pushup(int pos) { merge(t[pos].v, t[lc(pos)].v, t[rc(pos)].v); }
void build(int pos, int l, int r) {
  t[pos].l = l;
  t[pos].r = r;
  if (l == r) {
    t[pos].v.k.push_back(a[l]);
    t[pos].v.b.push_back(a[l] * l - sum[l]);
    t[pos].v.len = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(lc(pos), l, mid);
  build(rc(pos), mid + 1, r);
  pushup(pos);
}
int query(int pos, int l, int r, int x) {
  if (t[pos].l == l && t[pos].r == r) return t[pos].v.get(x);
  int mid = (t[pos].l + t[pos].r) >> 1;
  if (r <= mid)
    return query(lc(pos), l, r, x);
  else if (l > mid)
    return query(rc(pos), l, r, x);
  else
    return min(query(lc(pos), l, mid, x), query(rc(pos), mid + 1, r, x));
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
  build(1, 1, n);
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    cout << query(1, y - x + 1, y, x - y) + sum[y] << endl;
  }
  return 0;
}
