#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int inf = 1000000009;
int rd() {
  char c = getchar();
  int t = 0, f = 1;
  while (!isdigit(c)) f = (c == '-') ? -1 : 1, c = getchar();
  while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * f;
}
void wt(int x) {
  if (x < 0)
    putchar('-'), wt(-x);
  else {
    if (x > 9) wt(x / 10);
    putchar(x % 10 + 48);
  }
}
long long s[N], Ans[N];
vector<pair<int, int> > vec[N];
int n, m, A[N], l, r, mid, x, id, top, Res, stk[N];
double slope(int j, int k) {
  return 1.0 * ((s[k] - 1ll * A[k] * k) - (s[j] - 1ll * A[j] * j)) /
         (A[k] - A[j]);
}
int main() {
  n = rd();
  for (int i = ((int)1); i <= ((int)n); i++)
    A[i] = rd(), s[i] = s[i - 1] + A[i];
  m = rd();
  for (int i = ((int)1); i <= ((int)m); i++) {
    l = rd(), r = rd();
    vec[r].push_back(make_pair(l, i));
  }
  for (int i = ((int)1); i <= ((int)n); i++) {
    while (top > 0 && A[i] <= A[stk[top]]) top--;
    while (top > 1 && slope(i, stk[top]) >= slope(stk[top], stk[top - 1]))
      top--;
    stk[++top] = i;
    for (int j = ((int)0); j <= ((int)vec[i].size() - 1); j++) {
      x = vec[i][j].first, id = vec[i][j].second;
      l = lower_bound(stk + 1, stk + top + 1, i - x + 1) - stk;
      r = top - 1, Res = i;
      while (l <= r) {
        mid = l + r >> 1;
        if (slope(stk[mid], stk[mid + 1]) <= x - i)
          r = mid - 1, Res = stk[mid];
        else
          l = mid + 1;
      }
      Ans[id] = (s[i] - s[Res]) + 1ll * A[Res] * (x - i + Res);
    }
  }
  for (int i = ((int)1); i <= ((int)m); i++) printf("%I64d\n", Ans[i]);
  return 0;
}
