#include <bits/stdc++.h>
using namespace std;
struct Line {
  long long m, b;
};
bool super(Line &l1, Line &l2, Line &l3) {
  return (l3.b - l2.b) * (l1.m - l2.m) <= (l2.b - l1.b) * (l2.m - l3.m);
}
bool interLess(Line &lhs, Line &rhs, long long x) {
  return (rhs.b - lhs.b) < x * (lhs.m - rhs.m);
}
bool interGreater(Line &lhs, Line &rhs, long long x) {
  return (lhs.b - rhs.b) > x * (rhs.m - lhs.m);
}
Line al[100000];
struct LineHull {
  vector<int> stack;
  int sz;
  void insert(int il) {
    if ((sz >= 1) && (al[il].m == al[stack[sz - 1]].m)) {
      if (al[il].b < al[stack[sz - 1]].b) {
        sz--;
        stack.pop_back();
      } else
        return;
    }
    while ((sz >= 2) && (super(al[stack[sz - 2]], al[stack[sz - 1]], al[il]))) {
      stack.pop_back();
      sz--;
    }
    stack.push_back(il);
    sz++;
  }
  long long lowVal(long long x) {
    int low = 0;
    int high = sz - 1;
    int mid;
    while (low <= high) {
      mid = (low + high) / 2;
      if ((mid < (sz - 1)) &&
          (interLess(al[stack[mid]], al[stack[mid + 1]], x)))
        low = mid + 1;
      else if ((mid > 0) &&
               (interGreater(al[stack[mid]], al[stack[mid - 1]], x)))
        high = mid - 1;
      else
        return al[stack[mid]].m * x + al[stack[mid]].b;
    }
    return 1000000000;
  }
};
LineHull seg[2 * (1 << 17)];
int l[2 * (1 << 17)], r[2 * (1 << 17)];
void init() {
  for (int i = (1 << 17); i < 2 * (1 << 17); i++) {
    seg[i].sz = 0;
    l[i] = r[i] = i - (1 << 17);
  }
  for (int i = (1 << 17) - 1; i > 0; i--) {
    l[i] = l[2 * i];
    r[i] = r[2 * i + 1];
    seg[i].sz = 0;
  }
}
void add(int il) {
  for (int i = il + (1 << 17); i > 0; i /= 2) seg[i].insert(il);
}
int lo, hi;
long long x;
long long getMin(int i) {
  if ((l[i] >= lo) && (r[i] <= hi))
    return seg[i].lowVal(x);
  else if (hi <= r[i << 1])
    return getMin(i << 1);
  else if (lo > r[i << 1])
    return getMin(1 + (i << 1));
  else
    return min(getMin(i << 1), getMin(1 + (i << 1)));
}
long long A[100000];
long long sm[100000];
int aid[100000];
bool cmp(int a, int b) { return A[a] > A[b]; }
int main() {
  int N, Q;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) scanf("%I64d", &A[i]);
  sm[0] = A[0];
  for (int i = 1; i < N; i++) sm[i] = sm[i - 1] + A[i];
  for (int i = 0; i < N; i++) {
    al[i].m = A[i];
    al[i].b = i * A[i] - sm[i];
  }
  for (int i = 0; i < N; i++) aid[i] = i;
  sort(aid, aid + N, cmp);
  init();
  for (int i = 0; i < N; i++) add(aid[i]);
  scanf("%d", &Q);
  int a, b;
  for (int i = 0; i < Q; i++) {
    scanf("%d %d", &a, &b);
    b--;
    lo = b + 1 - a;
    hi = b;
    x = a - b;
    printf("%I64d\n", sm[b] + getMin(1));
  }
  return 0;
}
