#include <bits/stdc++.h>
using namespace std;
int R[300010 * 2], L[300010 * 2], n, m, sum[300010], sz;
struct Fun {
  int k, b;
} f[300010], id[300010 * 20], s[300010];
inline int Read() {
  char c = getchar();
  int num = 0, f = 1;
  while ('0' > c || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') num = num * 10 + c - '0', c = getchar();
  return (num * f);
}
inline bool Pd(Fun c, Fun a, Fun b) {
  return ((long long)(c.b - a.b) * (b.k - c.k) <=
          (long long)(c.b - b.b) * (a.k - c.k));
}
inline void Ins(int rt, Fun x) {
  id[++sz] = x;
  if (!R[rt]) L[rt] = sz;
  R[rt] = sz;
  while (R[rt] - L[rt] >= 2 && Pd(id[R[rt] - 2], id[R[rt] - 1], id[R[rt]])) {
    id[R[rt] - 1] = id[R[rt]];
    id[R[rt]] = (Fun){0, 0};
    sz--;
    R[rt]--;
  }
}
inline void Merge(int rt, int l, int mid, int r) {
  int i = l, j = mid + 1, k = l - 1;
  while (i <= mid && j <= r) {
    if ((f[i].k < f[j].k) || (f[i].k == f[j].k && f[i].b < f[j].b))
      s[++k] = f[i], i++;
    else
      s[++k] = f[j], j++;
  }
  for (; j <= r; j++) s[++k] = f[j];
  for (; i <= mid; i++) s[++k] = f[i];
  f[l] = s[l];
  Ins(rt, f[l]);
  for (int t = l + 1; t <= r; t++) {
    f[t] = s[t];
    if (f[t].k != f[t - 1].k) Ins(rt, f[t]);
  }
}
inline void Build(int rt, int l, int r) {
  int mid = (l + r) / 2;
  if (l == r) {
    Ins(rt, f[l]);
    return;
  }
  Build(rt * 2, l, mid);
  Build(rt * 2 + 1, mid + 1, r);
  Merge(rt, l, mid, r);
}
inline int Cal(int l, int r, int x) {
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (id[mid].k * x + id[mid].b < id[mid + 1].k * x + id[mid + 1].b) {
      r = mid;
      continue;
    }
    if (id[mid].k * x + id[mid].b > id[mid + 1].k * x + id[mid + 1].b) {
      l = mid;
      continue;
    }
    if (id[mid].k * x + id[mid].b < id[mid - 1].k * x + id[mid - 1].b) {
      l = mid;
      continue;
    }
    if (id[mid].k * x + id[mid].b > id[mid - 1].k * x + id[mid - 1].b) {
      r = mid;
      continue;
    }
  }
  return (min(id[l].k * x + id[l].b, id[r].k * x + id[r].b));
}
inline int Find(int rt, int l, int r, int a, int b, int p) {
  int mid = (l + r) / 2;
  if (l == a && r == b) {
    if (l <= 115 && 115 <= r) int deb = 0;
    return (Cal(L[rt], R[rt], p));
  }
  if (b <= mid) return (Find(rt * 2, l, mid, a, b, p));
  if (mid < a) return (Find(rt * 2 + 1, mid + 1, r, a, b, p));
  if (a <= mid && mid < b) {
    int L = Find(rt * 2, l, mid, a, mid, p);
    int R = Find(rt * 2 + 1, mid + 1, r, mid + 1, b, p);
    return (min(L, R));
  }
}
int main() {
  n = Read();
  for (int i = 1; i <= n; i++) f[i].k = Read();
  for (int i = 1; i <= n; i++)
    sum[i] = sum[i - 1] + f[i].k, f[i].b = f[i].k * i - sum[i];
  Build(1, 1, n);
  m = Read();
  for (int i = 1; i <= m; i++) {
    int x = Read(), y = Read();
    int Min = Find(1, 1, n, y - x + 1, y, x - y);
    printf("%d\n", min(sum[y] - sum[y - x], sum[y] + Min));
  }
}
