#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  long long r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long fpow(long long n, long long k, int p = (int)1e9 + 7) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = 2 * acos((long double)0);
struct Convexhull {
  struct Line {
    long long a, b;
    Line(long long a, long long b) : a(a), b(b) {}
  };
  long double intersect(Line ln1, Line ln2) {
    return (long double)(ln2.b - ln1.b) / (ln1.a - ln2.a);
  }
  int bad(Line ln1, Line ln2, Line ln3) {
    return (long double)(ln1.a - ln2.a) * (ln2.b - ln3.b) >=
           (long double)(ln2.a - ln3.a) * (ln1.b - ln2.b);
  }
  vector<Line> hull;
  vector<long double> pos;
  Convexhull() {
    pos.push_back(-1e18);
    pos.push_back(+1e18);
  }
  void add(long long a, long long b) {
    Line ln(a, b);
    pos.pop_back();
    while (hull.size() >= 2 &&
           bad(hull[hull.size() - 2], hull[hull.size() - 1], ln)) {
      hull.pop_back();
      pos.pop_back();
    }
    hull.push_back(ln);
    if (hull.size() >= 2)
      pos.push_back(intersect(hull[hull.size() - 2], hull[hull.size() - 1]));
    pos.push_back(+1e18);
  }
  long long query(long long x) {
    if (!hull.size()) return 1e18;
    int k = lower_bound(pos.begin(), pos.end(), x) - pos.begin() - 1;
    return hull[k].a * x + hull[k].b;
  }
};
const int maxn = 100010;
int n;
int a[maxn];
long long sum[maxn];
Convexhull st[4 * maxn];
void update(int node, int i, int L, int R, long long a, long long b) {
  if (i < L || i > R) return;
  st[node].add(a, b);
  if (L == R) return;
  update(node << 1, i, L, (L + R) >> 1, a, b);
  update((node << 1) + 1, i, ((L + R) >> 1) + 1, R, a, b);
}
long long query(int node, int l, int r, int L, int R, long long x) {
  if (l > R || r < L) return 1e18;
  if (l <= L && r >= R) return st[node].query(x);
  return min(query(node << 1, l, r, L, (L + R) >> 1, x),
             query((node << 1) + 1, l, r, ((L + R) >> 1) + 1, R, x));
}
void solve() {
  scanf("%d", &n);
  for (int i = (1); i < (n + 1); i++) {
    scanf("%d", a + i);
    sum[i] = sum[i - 1] + a[i];
  }
  vector<pair<pair<long long, long long>, int> > vl;
  for (int i = (1); i < (n + 1); i++) {
    vl.push_back(make_pair(make_pair(a[i], (long long)i * a[i] - sum[i]), i));
  }
  sort((vl).begin(), (vl).end());
  for (int i = (int((vl).size())) - 1; i >= (0); i--) {
    update(1, vl[i].second, 1, n, vl[i].first.first, vl[i].first.second);
  }
  int m;
  scanf("%d", &m);
  while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    printf("%d\n", query(1, v - u, v, 1, n, u - v) + sum[v]);
  }
}
int main() {
  solve();
  return 0;
}
