#include <bits/stdc++.h>
using namespace std;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
const int INF = 5e8;
const long long int INF2 = 1e18;
int n;
int ar[100005];
pair<long long int, long long int> ar2[100005];
bool cmp(const pair<long long int, long long int>& a,
         const pair<long long int, long long int>& b) {
  if (a.second != b.second) return a.second < b.second;
  return a.first < b.first;
}
struct segtree {
  vector<pair<long long int, long long int> > val[400005];
  int n;
  double cross(const pair<long long int, long long int>& a,
               const pair<long long int, long long int>& b) {
    return (a.second - b.second) / (double)(b.first - a.first);
  }
  void fix(vector<pair<long long int, long long int> >& a) {
    sort((a).begin(), (a).end(), cmp);
    int gradmin = INF;
    vector<pair<long long int, long long int> > res;
    for (int i = 0; i < (a.size()); ++i) {
      if (a[i].first >= gradmin) continue;
      pair<long long int, long long int> cur = a[i];
      if (res.size() <= 1)
        res.push_back(cur);
      else {
        while (res.size() >= 2) {
          if (cross(res[res.size() - 2], res.back()) >=
              cross(res.back(), cur)) {
            res.pop_back();
          } else
            break;
        }
        res.push_back(cur);
      }
      chmin(gradmin, (int)a[i].first);
    }
    a = res;
  }
  void init(int n_) {
    n = 1;
    while (n < n_) n <<= 1;
    for (int i = 0; i < (n_); ++i) val[i + n - 1].push_back(ar2[i]);
    for (int i = n - 2; i >= 0; --i) {
      val[i].insert(val[i].end(), (val[i * 2 + 1]).begin(),
                    (val[i * 2 + 1]).end());
      val[i].insert(val[i].end(), (val[i * 2 + 2]).begin(),
                    (val[i * 2 + 2]).end());
      fix(val[i]);
    }
  }
  long long int getval(const vector<pair<long long int, long long int> >& a,
                       long long int T) {
    int lb = 0, ub = a.size();
    while (ub - lb > 1) {
      int md = (lb + ub) >> 1;
      if (cross(a[md - 1], a[md]) > T)
        ub = md;
      else
        lb = md;
    }
    return a[lb].first * T + a[lb].second;
  }
  long long int query(int a, int b, int i, int l, int r, int T) {
    if (a <= l && r <= b) {
      return getval(val[i], T);
    }
    if (b <= l || r <= a) return INF2;
    int md = (l + r) >> 1;
    return min(query(a, b, i * 2 + 1, l, md, T),
               query(a, b, i * 2 + 2, md, r, T));
  }
};
segtree seg;
int latsum[100005];
int main() {
  cin >> n;
  for (int i = 0; i < (n); ++i) scanf("%d", &ar[i]);
  for (int i = n - 1; i >= 0; --i) latsum[i] = latsum[i + 1] + ar[i];
  for (int i = n - 1; i >= 0; --i) {
    ar2[i].second = latsum[i + 1];
    ar2[i].first = ar[i];
  }
  for (int i = 0; i < (n); ++i) {
    ar2[i].second -= (n - i - 1) * ar[i];
  }
  seg.init(n);
  int q;
  cin >> q;
  for (int hoge = 0; hoge < (q); ++hoge) {
    int x, y;
    scanf("%d%d", &y, &x);
    --x;
    --y;
    int d = n - 1 - x;
    int l = x - y, r = x + 1;
    x += d;
    y += d;
    long long int res = seg.query(l, r, 0, 0, seg.n, y + 1);
    res -= latsum[r];
    cout << res << endl;
  }
  return 0;
}
