#include <bits/stdc++.h>
using namespace std;
inline int Get() {
  int res = 0, q = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') q = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
  return res * q;
}
const double eps = 1e-12, pi = M_PI;
const int oo = (int)2e9, mod = (int)1e9 + 7;
const long long INF = (long long)1e17;
const int N = (int)3e5;
typedef long long arr[N + 10];
vector<long long> v[N + 10];
arr a, b, s, nd, st;
long long n, m, top;
bool cmp(const long long &x, const long long &y) {
  return a[x] < a[y] || (a[x] == a[y] && b[x] < b[y]);
}
long long Cross(long long x1, long long y1, long long x2, long long y2) {
  return x1 * y2 - x2 * y1;
}
void Convex() {
  sort(nd + 1, nd + m + 1, cmp);
  top = 0;
  for (int i = (1), end = (m); i <= end; ++i) {
    for (; top > 1 && Cross(a[nd[i]] - a[st[top]], b[nd[i]] - b[st[top]],
                            a[st[top]] - a[st[top - 1]],
                            b[st[top]] - b[st[top - 1]]) >= 0;)
      --top;
    st[++top] = nd[i];
  }
}
void Build(long long l, long long r, long long x) {
  if (l == r) {
    v[x].push_back(l), v[x].push_back(n + 1);
    return;
  }
  long long mid = (l + r) >> 1;
  Build(l, mid, x << 1), Build(mid + 1, r, x << 1 | 1);
  m = 0;
  long long ls = x << 1, rs = x << 1 | 1, sz = ((int)v[ls].size());
  for (int i = (0), end = (sz - 2); i <= end; ++i) nd[++m] = v[ls][i];
  sz = ((int)v[rs].size());
  for (int i = (0), end = (sz - 2); i <= end; ++i) nd[++m] = v[rs][i];
  Convex();
  for (int i = (1), end = (top); i <= end; ++i) v[x].push_back(st[i]);
  v[x].push_back(n + 1);
}
long long Calc(long long x, long long k) { return a[x] * k + b[x]; }
long long Divide(long long x, long long k) {
  long long l = 0, r = ((int)v[x].size()) - 2;
  for (; l <= r;) {
    long long mid = (l + r) >> 1;
    if (Calc(v[x][mid], k) > Calc(v[x][mid + 1], k))
      l = mid + 1;
    else
      r = mid - 1;
  }
  if (r < 0)
    return Calc(v[x][l], k);
  else if (l >= ((int)v[x].size()) - 1)
    return Calc(v[x][r], k);
  else
    return min(Calc(v[x][r], k), Calc(v[x][l], k));
}
long long Query(long long l, long long r, long long x, long long ml,
                long long mr, long long k) {
  if (l >= ml && r <= mr) return Divide(x, k);
  long long mid = (l + r) >> 1, res = INF;
  if (ml <= mid) res = min(res, Query(l, mid, x << 1, ml, mr, k));
  if (mr > mid) res = min(res, Query(mid + 1, r, x << 1 | 1, ml, mr, k));
  return res;
}
int main() {
  scanf(
      "%I64d"
      "\n",
      &n);
  for (int i = (1), end = (n); i <= end; ++i)
    scanf(
        "%I64d"
        "\n",
        a + i),
        s[i] = s[i - 1] + a[i], b[i] = a[i] * i - s[i];
  Build(1, n, 1), b[n + 1] = -INF;
  for (scanf("%I64d"
             "\n",
             &m);
       m; --m) {
    long long x, y;
    scanf(
        "%I64d"
        "%I64d"
        "\n",
        &x, &y);
    printf(
        "%I64d"
        "\n",
        s[y] + Query(1, n, 1, y - x + 1, y, x - y));
  }
  return 0;
}
