#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
const int M = 2001000;
struct func {
  int k, b;
} c[M], st[M], f[M];
int n, m, a[N], sum[N];
int low[M], top[M], minans, tot;
bool isok(func x, func y, func z) {
  return (long long)(z.b - x.b) * (x.k - y.k) >=
         (long long)(y.b - x.b) * (x.k - z.k);
}
void add(int i, func t) {
  st[++tot] = t;
  if (!low[i])
    low[i] = top[i] = tot;
  else
    top[i]++;
  while (top[i] - 2 >= low[i]) {
    if (!isok(st[tot - 2], st[tot - 1], st[tot])) break;
    st[tot - 1] = st[tot];
    tot--;
    top[i]--;
  }
}
void merge(int t, int l1, int r1, int l2, int r2) {
  int i, j, k = l1 - 1, l = l1, r = r2;
  while (l1 <= r1 && l2 <= r2) {
    if (c[l1].k < c[l2].k || (c[l1].k == c[l2].k && c[l1].b < c[l2].b))
      f[++k] = c[l1++];
    else
      f[++k] = c[l2++];
  }
  while (l1 <= r1) f[++k] = c[l1++];
  while (l2 <= r2) f[++k] = c[l2++];
  add(t, f[l]);
  for (i = l + 1; i <= r; i++)
    if (f[i].k != f[i - 1].k) add(t, f[i]);
  for (i = l; i <= r; i++) c[i] = f[i];
}
void build(int i, int l, int r) {
  if (l == r) {
    add(i, c[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  merge(i, l, mid, mid + 1, r);
}
int F(func t, int x) { return t.k * x + t.b; }
void check(int i, int x) {
  int l = low[i], r = top[i], mid, tmp;
  while (r - l > 1) {
    mid = (l + r) >> 1;
    if (F(st[mid], x) < F(st[mid + 1], x))
      r = mid;
    else if (F(st[mid], x) > F(st[mid + 1], x))
      l = mid;
    else if (F(st[mid - 1], x) < F(st[mid], x))
      r = mid;
    else
      l = mid;
  }
  tmp = F(st[l], x);
  minans = min(minans, tmp);
  tmp = F(st[r], x);
  minans = min(minans, tmp);
}
void query(int i, int l, int r, int x, int y, int z) {
  if (x <= l && y >= r) {
    check(i, z);
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) query(i << 1, l, mid, x, y, z);
  if (y > mid) query(i << 1 | 1, mid + 1, r, x, y, z);
}
int main() {
  int i, x, y;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    sum[i] = sum[i - 1] + a[i];
    c[i].k = a[i];
    c[i].b = a[i] * i - sum[i];
  }
  build(1, 1, n);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    x = y - x;
    minans = 2000000000;
    query(1, 1, n, x, y, -x);
    printf("%d\n", min(sum[y] + minans, sum[y] - sum[x - 1]));
  }
  return 0;
}
