#include <bits/stdc++.h>
using namespace std;
const int N = 100100, INF = 1e8 + 10;
int n, a[N], prf[N];
inline bool isbad(int ktop, int btop, int k, int b, int kk, int bb) {
  if (ktop == kk && btop >= bb) return true;
  return (long long)(b - bb) * (ktop - k) <= (long long)(b - btop) * (kk - k);
}
struct convex_hull {
  int *k, *b;
  int len;
  convex_hull() { len = 0; }
  void add_line(const int& kk, const int& bb) {
    while (len >= 2 && isbad(k[len], b[len], k[len - 1], b[len - 1], kk, bb))
      --len;
    while (len >= 1 && k[len] == kk && b[len] > bb) --len;
    if (len >= 1 && k[len] == kk && b[len] <= bb) return;
    k[++len] = kk;
    b[len] = bb;
  }
  int get_val(int idx, int x) { return k[idx] * x + b[idx]; }
  int ask_min(int x) {
    int lo = 0, hi = len, mid;
    while (hi - lo > 1) {
      mid = lo + hi >> 1;
      if (get_val(mid, x) >= get_val(mid + 1, x))
        lo = mid;
      else
        hi = mid;
    }
    return get_val(hi, x);
  }
} t[4 * N];
inline void merge_convex_hulls(int res, int a, int b) {
  t[res].len = 0;
  t[res].k = new int[t[a].len + t[b].len + 1];
  t[res].b = new int[t[a].len + t[b].len + 1];
  int i = 1, j = 1;
  while (i <= t[a].len && j <= t[b].len) {
    if (t[a].k[i] > t[b].k[j]) {
      t[res].add_line(t[a].k[i], t[a].b[i]);
      ++i;
    } else {
      t[res].add_line(t[b].k[j], t[b].b[j]);
      ++j;
    }
  }
  for (; i <= t[a].len; i++) t[res].add_line(t[a].k[i], t[a].b[i]);
  for (; j <= t[b].len; j++) t[res].add_line(t[b].k[j], t[b].b[j]);
}
inline void build(int i, int lo, int hi) {
  if (lo == hi) {
    t[i].k = new int[2];
    t[i].b = new int[2];
    t[i].k[1] = a[lo];
    t[i].b[1] = a[lo] * lo - prf[lo];
    t[i].len = 1;
    return;
  }
  int mid = lo + hi >> 1, c1 = i << 1, c2 = c1 | 1;
  build(c1, lo, mid);
  build(c2, mid + 1, hi);
  merge_convex_hulls(i, c1, c2);
}
inline int ask(int i, int lo, int hi, int ql, int qr, int qx) {
  if (hi < ql || qr < lo) return INF;
  if (ql <= lo && hi <= qr) return t[i].ask_min(qx);
  int mid = lo + hi >> 1, c1 = i << 1, c2 = c1 | 1;
  return min(ask(c1, lo, mid, ql, qr, qx), ask(c2, mid + 1, hi, ql, qr, qx));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    prf[i] = prf[i - 1] + a[i];
  }
  build(1, 1, n);
  int q, x, y;
  for (scanf("%d", &q); q--;) {
    scanf("%d%d", &x, &y);
    printf("%d\n", ask(1, 1, n, y - x + 1, y, x - y) + prf[y]);
  }
  return 0;
}
