#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct dreapta {
  ll a, b;
  ll operator()(ll x) { return a * x + b; }
};
bool useless(const dreapta& x, const dreapta& y, const dreapta& z) {
  return (x.b - y.b) * (z.a - x.a) >= (x.b - z.b) * (y.a - x.a);
}
class batch {
  vector<dreapta> v;

 public:
  batch() {}
  void add(const dreapta& d) {
    while (v.size() >= 2 && useless(v.rbegin()[1], v.back(), d)) v.pop_back();
    v.push_back(d);
  }
  ll query(ll x) {
    while (v.size() >= 2 && v.rbegin()[1](x) <= v.back()(x)) v.pop_back();
    return v.back()(x);
  }
};
class arbint {
  ll n;
  vector<batch> v;

 public:
  arbint(ll N) : n(N), v(2 * n) {}
  void add(ll st, const dreapta& d) {
    for (st += n; st; st /= 2) v[st].add(d);
  }
  ll query(ll st, ll dr, ll x) {
    ll ret = (ll)1e9 * (ll)1e9;
    for (st += n, dr += n + 1; st < dr; st /= 2, dr /= 2) {
      if (st % 2) ret = min(ret, v[st++].query(x));
      if (dr % 2) ret = min(ret, v[--dr].query(x));
    }
    return ret;
  }
};
int main() {
  ll n;
  cin >> n;
  vector<ll> v(n);
  for (auto& x : v) cin >> x;
  vector<ll> sp_v(n);
  partial_sum(begin(v), end(v), begin(sp_v));
  vector<ll> v_by_ord(n);
  iota(begin(v_by_ord), end(v_by_ord), 0);
  sort(begin(v_by_ord), end(v_by_ord), [&](ll x, ll y) { return v[x] > v[y]; });
  arbint a(n);
  for (auto i : v_by_ord) {
    a.add(i, dreapta{v[i], v[i] * i - sp_v[i]});
  }
  ll m;
  cin >> m;
  struct query {
    ll timp, dr, ret;
  };
  vector<query> qs(m);
  for (auto& q : qs) cin >> q.timp >> q.dr, --q.dr;
  vector<ll> qs_by_ord(m);
  iota(begin(qs_by_ord), end(qs_by_ord), 0);
  sort(begin(qs_by_ord), end(qs_by_ord), [&](ll x, ll y) {
    return qs[x].timp - qs[x].dr > qs[y].timp - qs[y].dr;
  });
  for (auto q : qs_by_ord) {
    qs[q].ret =
        a.query(qs[q].dr - qs[q].timp + 1, qs[q].dr, qs[q].timp - qs[q].dr) +
        sp_v[qs[q].dr];
  }
  for (auto q : qs) cout << q.ret << '\n';
  return 0;
}
