#include <bits/stdc++.h>
using namespace std;
namespace Stand_IO_Operation {
inline int read() {
  int f = 1, res = 0, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') res = res * 10 + ch - 48, ch = getchar();
  return f * res;
}
int _sta[1 << 8];
inline void write(int val) {
  if (!val) {
    putchar('0');
    return;
  }
  if (val < 0) putchar('-'), val = -val;
  *_sta = 0;
  while (val > 0) _sta[++*_sta] = val % 10, val /= 10;
  for (int i = *_sta, _Lim = 1; i >= _Lim; i--) putchar(_sta[i] + 48);
}
};  // namespace Stand_IO_Operation
using namespace Stand_IO_Operation;
const int N = 100005;
vector<pair<int, int> > Q[N];
int n, q, A[N], Sum[N], Ans[N];
inline double Slope(int a, int b) {
  double Vala = Sum[a] - 1.0 * a * A[a];
  double Valb = Sum[b] - 1.0 * b * A[b];
  return (Vala - Valb) / (A[a] - A[b]);
}
int S[N];
int main() {
  scanf("%d", &n);
  for (int i = 1, _Lim = n; i <= _Lim; i++) A[i] = read();
  q = read();
  for (int i = 1, _Lim = q; i <= _Lim; i++) {
    int x = read(), y = read();
    Q[y].push_back(make_pair(x, i));
  }
  for (int i = 1, _Lim = n; i <= _Lim; i++) {
    Sum[i] = Sum[i - 1] + A[i];
    while (*S > 0 && A[i] <= A[S[*S]]) --*S;
    while (*S > 1 && Slope(S[*S], i) >= Slope(S[*S - 1], i)) --*S;
    S[++*S] = i;
    for (int ter = 0; ter < Q[i].size(); ter++) {
      int pos = Q[i][ter].first;
      int bak = Q[i][ter].second;
      int L = lower_bound(S + 1, S + *S + 1, i - pos + 1) - S;
      int R = *S - 1, res = S[*S];
      while (L <= R) {
        int mid = (L + R) >> 1;
        if (Slope(S[mid], S[mid + 1]) <= pos - i) {
          res = S[mid];
          R = mid - 1;
        } else
          L = mid + 1;
      }
      Ans[bak] = Sum[i] - Sum[res] + (pos - (i - res)) * A[res];
    }
  }
  for (int i = 1, _Lim = q; i <= _Lim; i++) write(Ans[i]), putchar(10);
}
