#include <bits/stdc++.h>
using namespace std;
inline long long ma(long long a, long long b) { return a > b ? a : b; }
inline long long mi(long long a, long long b) { return a > b ? b : a; }
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
vector<long long> adj[100005], v;
bool Q;
struct line {
  mutable long long k, m, p;
  bool operator<(const line &o) const { return Q ? p < o.p : k < o.k; }
};
struct LineContainer : multiset<line> {
  const long long inf = LLONG_MAX;
  inline long long div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b);
  }
  inline bool isect(iterator x, iterator y) {
    if (y == end()) {
      x->p = inf;
      return false;
    }
    if (x->k == y->k)
      x->p = x->m > y->m ? inf : -inf;
    else
      x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  inline void add(long long k, long long m) {
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (y != begin() && isect(--x, y)) isect(x, erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
  }
  inline long long query(long long x) {
    assert(!empty());
    Q = 1;
    auto l = *lower_bound({0, 0, x});
    Q = 0;
    return l.k * x + l.m;
  }
};
struct T {
  LineContainer lc;
  T() {}
  T(LineContainer &lc) : lc(lc) {}
};
struct ST {
  long long n;
  T t[2 * 100005];
  inline void Op(T &ty, T &val1, T &val2) {
    for (auto xd : val1.lc) {
      ty.lc.add(xd.k, xd.m);
    }
    for (auto xd : val2.lc) {
      ty.lc.add(xd.k, xd.m);
    }
  }
  inline long long Op1(T &val1, long long cur, long long x) {
    long long val = val1.lc.query(x);
    return mi(cur, -val);
  }
  inline void build() {
    for (long long(i) = (n - 1); (i) >= (1); (i)--)
      Op(t[i], t[i << 1], t[i << 1 | 1]);
  }
  inline long long que(long long l, long long r, long long ra) {
    long long ans = 23242532523;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans = Op1(t[l++], ans, ra);
      if (r & 1) ans = Op1(t[--r], ans, ra);
    }
    return ans;
  }
};
long long dp[100005], ar[100005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  long long n;
  cin >> n;
  ST st;
  st.n = n;
  for (long long(i) = (0); (i) < (n); (i)++) cin >> ar[i];
  for (long long(i) = (0); (i) < (n); (i)++)
    dp[i] = (i == 0) ? ar[i] : dp[i - 1] + ar[i];
  for (long long(i) = (0); (i) < (n); (i)++) {
    long long x = ar[i], y = ar[i] * (i + 1) - dp[i];
    st.t[i + n].lc.add(-x, -y);
  }
  st.build();
  long long q;
  cin >> q;
  vector<pair<long long, pair<long long, long long> > > qs;
  for (long long(i) = (0); (i) < (q); (i)++) {
    long long l, r;
    cin >> l >> r;
    l--;
    qs.push_back({l - r + 1, {i, r}});
  }
  sort((qs).begin(), (qs).end());
  reverse((qs).begin(), (qs).end());
  long long ez[100005];
  for (long long(i) = (0); (i) < (qs.size()); (i)++) {
    long long val = qs[i].first, r = qs[i].second.second,
              id = qs[i].second.first;
    long long l = val + r;
    l = r - l;
    ez[id] = st.que(l, r, val) + dp[r - 1];
  }
  for (long long(i) = (0); (i) < (q); (i)++) cout << ez[i] << endl;
  return 0;
}
