#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  return is >> p.first >> p.second;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
  return os << p.first << " " << p.second;
}
const long long inf = 2000000000ll * 1000000000;
const long long N = 100005;
struct line {
  long long k, b;
  line(long long k = 0, long long b = inf) : k(k), b(b) {}
  long long eval(long long x) { return k * x + b; }
};
struct lichao {
  long long tl, tr;
  line cur_line;
  lichao *l, *r;
  lichao(long long tl, long long tr)
      : tl(tl), tr(tr), cur_line(line()), l(0), r(0) {}
  void make_children() {
    if (tl < tr) {
      long long tm = (tl + tr) >> 1;
      if (!l) l = new lichao(tl, tm);
      if (!r) r = new lichao(tm + 1, tr);
    }
  }
  void add_line(line new_line) {
    line a = cur_line, b = new_line;
    if (a.eval(tl) < b.eval(tl)) swap(a, b);
    if (a.eval(tr) >= b.eval(tr))
      cur_line = b;
    else if (tl < tr) {
      make_children();
      long long tm = (tl + tr) >> 1;
      if (a.eval(tm) < b.eval(tm))
        cur_line = a, l->add_line(b);
      else
        cur_line = b, r->add_line(a);
    }
  }
  long long get_min(long long x) {
    long long res = cur_line.eval(x);
    long long tm = (tl + tr) >> 1;
    if (x <= tm)
      res = min(res, l ? l->get_min(x) : inf);
    else
      res = min(res, r ? r->get_min(x) : inf);
    return res;
  }
};
lichao *t[N << 2];
void update(long long v, long long tl, long long tr, long long pos, long long k,
            long long b) {
  if (!t[v]) t[v] = new lichao(-N, N);
  t[v]->add_line({k, b});
  if (tl == tr) return;
  long long tm = (tl + tr) >> 1;
  if (pos <= tm)
    update(v + v, tl, tm, pos, k, b);
  else
    update(v + v + 1, tm + 1, tr, pos, k, b);
}
long long get_min(long long v, long long tl, long long tr, long long l,
                  long long r, long long x) {
  if (tl > tr || l > r || l > tr || tl > r) return inf;
  if (tl >= l && tr <= r) return t[v]->get_min(x);
  long long tm = (tl + tr) >> 1;
  return min(get_min(v + v, tl, tm, l, r, x),
             get_min(v + v + 1, tm + 1, tr, l, r, x));
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<long long> v(n);
  vector<long long> sum(n);
  for (long long i = 0; i < n; i++) {
    cin >> v[i];
    sum[i] += v[i];
    if (i + 1 < n) sum[i + 1] += sum[i];
  }
  for (long long i = 0; i < n; i++) {
    update(1, 0, n - 1, i, v[i], v[i] * i - sum[i]);
  }
  long long q;
  cin >> q;
  while (q--) {
    long long x, y;
    cin >> x >> y;
    y--;
    cout << sum[y] + get_min(1, 0, n - 1, y - x + 1, y, x - y) << "\n";
  }
}
