#include <bits/stdc++.h>
using namespace std;
bool query = 0;
struct line {
  long long m, b;
  mutable function<const line *()> succ;
  bool operator<(const line &rhs) const {
    if (!query) return m < rhs.m;
    const line *s = succ();
    return s ? (b - s->b) < rhs.m * (s->m - m) : 0;
  }
};
struct hull : multiset<line> {
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return 0;
      return (y->m == z->m) && (y->b <= z->b);
    }
    auto x = prev(y);
    if (z == end()) return (y->m == x->m) && (y->b <= x->b);
    return (1.0) * (x->b - y->b) * (z->m - y->m) >=
           (1.0) * (y->b - z->b) * (y->m - x->m);
  }
  void add(long long m, long long b) {
    auto it = insert({m, b});
    it->succ = [=] { return next(it) == end() ? 0 : &*next(it); };
    if (bad(it)) {
      erase(it);
      return;
    }
    while (next(it) != end() && bad(next(it))) erase(next(it));
    while (it != begin() && bad(prev(it))) erase(prev(it));
  }
  long long eval(long long x) {
    query = 1;
    auto l = *lower_bound({x, 0});
    query = 0;
    return l.m * x + l.b;
  }
};
hull h[4 * 100005];
int n, m;
long long a[100005], rsa[100005];
void build(int l = 1, int r = n, int p = 0) {
  if (l == r) {
    h[p].add(-a[l], -l * a[l] - rsa[l + 1]);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, (p << 1) | 1);
  build(mid + 1, r, (p << 1) + 2);
  for (auto x : h[(p << 1) | 1]) h[p].add(x.m, x.b);
  for (auto x : h[(p << 1) + 2]) h[p].add(x.m, x.b);
}
long long ask(int ql, int qr, int x, int l = 1, int r = n, int p = 0) {
  if (ql <= l && r <= qr) return -h[p].eval(x);
  if (r < ql || qr < l) return 1e18;
  int mid = (l + r) >> 1;
  return min(ask(ql, qr, x, l, mid, (p << 1) | 1),
             ask(ql, qr, x, mid + 1, r, (p << 1) + 2));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  for (int i = n; i >= 1; i--) rsa[i] = rsa[i + 1] + a[i];
  build();
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int I, J;
    scanf("%d%d", &I, &J);
    printf("%I64d\n", ask(J - I + 1, J, I - J) - rsa[J + 1]);
  }
}
