#include <bits/stdc++.h>
template <typename T>
inline void mini(T &a, T b) {
  if (a > b) a = b;
}
enum { n_max = 110000 };
struct Query {
  int i, x, y;
};
std::vector<Query> Q[n_max];
int A[n_max];
int P[n_max];
int H[n_max];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < (n); ++i) scanf("%d", A + i);
  int m;
  scanf("%d", &m);
  for (int i = 0; i < (m); ++i) {
    Query q{i};
    scanf("%d%d", &q.x, &q.y);
    Q[q.y - 1].push_back(q);
  }
  std::vector<int> R(m);
  std::vector<int> S;
  for (int i = 0; i < (n); ++i) {
    P[i] = A[i] + (i ? P[i - 1] : 0);
    H[i] = i + 1;
    while (S.size()) {
      if (A[S.back()] >= A[i]) {
        S.pop_back();
        continue;
      }
      int j = S.back();
      int p = P[i] - P[j];
      int h = (p + (j - i) * A[j]) / (A[i] - A[j]);
      if (h >= H[j] + (i - j)) {
        S.pop_back();
        continue;
      }
      mini(H[i], h);
      break;
    }
    S.push_back(i);
    for (Query q : Q[i]) {
      int l = 0, h = S.size() - 1;
      while (l < h) {
        int m = (l + h + 1) / 2;
        if (H[S[m]] + (i - S[m]) >= q.x)
          l = m;
        else
          h = m - 1;
      }
      R[q.i] = A[S[l]] * (q.x - (i - S[l])) + (P[i] - P[S[l]]);
    }
  }
  for (int r : R) printf("%d\n", r);
  return 0;
}
