#include <bits/stdc++.h>
using namespace std;
int n, nQuery;
long long x[100001];
int decToLeft[100001];
int leftNextSmall[100001];
int skipTo[100001];
long long sum[100001];
inline long long calc(int take, int L, int R) {
  return sum[R] - sum[L - 1] + x[L] * (take - (R - L + 1));
}
int MAIN() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> x[i];
  x[0] = -1;
  sum[0] = 0;
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + x[i];
  decToLeft[1] = 1;
  leftNextSmall[1] = 0;
  for (int i = 2; i <= n; i++) {
    if (x[i] < x[i - 1])
      decToLeft[i] = i;
    else
      decToLeft[i] = decToLeft[i - 1];
    int t = i - 1;
    while (x[t] >= x[i]) t = leftNextSmall[t];
    leftNextSmall[i] = t;
  }
  for (int i = 1; i <= n; i++) skipTo[i] = min(leftNextSmall[i], decToLeft[i]);
  cin >> nQuery;
  while (nQuery--) {
    int amount, R;
    cin >> amount >> R;
    int pos = R;
    long long ret = 1000000000000000000;
    while (true) {
      ret = min(ret, calc(amount, pos, R));
      if (R - pos + 1 == amount)
        break;
      else {
        pos = skipTo[pos];
        pos = max(pos, R - amount + 1);
      }
    }
    cout << ret << endl;
  }
  return 0;
}
int main() {
  ios ::sync_with_stdio(false);
  cout << fixed << setprecision(16);
  return MAIN();
}
