#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
const int MAXM = 2e5;
long long N, M;
long long first[MAXN];
pair<pair<long long, long long>, long long> Q[MAXM];
long long ans[MAXM];
vector<pair<pair<long long, long long>, pair<long long, long long>>> lines;
inline long long eval(pair<long long, long long> l, long long x) {
  return x * l.first + l.second;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> N;
  for (long long i = 1; i <= N; i++) {
    cin >> first[i];
  }
  cin >> M;
  for (long long i = 0; i < M; i++) {
    cin >> Q[i].first.second >> Q[i].first.first;
    Q[i].second = i;
  }
  sort(Q, Q + M);
  long long pref = 0;
  long long q = 0;
  for (long long j = 1; j <= N; j++) {
    pref += first[j];
    pair<long long, long long> cur(first[j], pref - j * first[j]);
    pair<long long, long long> range(0, j);
    while (!lines.empty()) {
      auto &l = lines.back();
      if (eval(cur, l.first.first) >= eval(l.second, l.first.first)) {
        lines.pop_back();
        continue;
      } else {
        long long mi = l.first.first;
        long long ma = l.first.second + 1;
        while (ma - mi > 1) {
          long long md = (mi + ma) / 2;
          if (eval(cur, md) >= eval(l.second, md)) {
            ma = md;
          } else {
            mi = md;
          }
        }
        l.first.second = mi;
        range.first = ma;
        break;
      }
    }
    lines.push_back(make_pair(range, cur));
    for (auto l : lines) {
    }
    while (q < M && Q[q].first.first == j) {
      long long i = j - Q[q].first.second;
      auto l = upper_bound(lines.begin(), lines.end(),
                           make_pair(pair<long long, long long>(i, j + 1),
                                     pair<long long, long long>(0, 0)));
      assert(l != lines.begin());
      l--;
      ans[Q[q].second] = pref - eval(l->second, i);
      q++;
    }
  }
  for (long long i = 0; i < M; i++) {
    cout << ans[i] << '\n';
  }
}
