#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005], s[100005];
struct cht {
  vector<pair<long long, long long> > tree[270000];
  int lim;
  long double cross(pair<long long, long long> a,
                    pair<long long, long long> b) {
    return (long double)(b.second - a.second) / (a.first - b.first);
  }
  bool check(pair<long long, long long> a, pair<long long, long long> b,
             pair<long long, long long> c) {
    return (a.second - b.second) * (c.first - b.first) >
           (b.second - c.second) * (b.first - a.first);
  }
  void get_hull(vector<pair<long long, long long> > &in,
                vector<pair<long long, long long> > &out) {
    for (auto &i : in) {
      while (out.size() >= 2 && check(out[out.size() - 2], out.back(), i)) {
        out.pop_back();
      }
      out.push_back(i);
    }
  }
  long long tquery(vector<pair<long long, long long> > &v, int x) {
    auto func = [&](pair<long long, long long> t, int x) {
      return t.first * x + t.second;
    };
    int s = 0, e = v.size() - 1;
    while (s != e) {
      int m = (s + e) / 2;
      if (func(v[m], x) < func(v[m + 1], x)) {
        e = m;
      } else
        s = m + 1;
    }
    return func(v[s], x);
  }
  void init() {
    for (lim = 1; lim <= n; lim <<= 1)
      ;
    for (int i = 1; i <= n; i++) {
      int p = i + lim;
      while (p >= 1) {
        tree[p].push_back(
            pair<long long, long long>(a[i], 1ll * a[i] * i - s[i]));
        p >>= 1;
      }
    }
    for (int i = 1; i <= 2 * lim; i++) {
      sort(tree[i].begin(), tree[i].end(),
           [&](const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
             if (a.first != b.first) return a.first > b.first;
             return a.second < b.second;
           });
      vector<pair<long long, long long> > tmp;
      long long cpos = -111;
      for (auto &j : tree[i]) {
        if (j.first == cpos) continue;
        cpos = j.first;
        tmp.push_back(j);
      }
      tree[i].clear();
      get_hull(tmp, tree[i]);
    }
  }
  long long query(int s, int e, int x) {
    s += lim;
    e += lim;
    long long ret = 1e18;
    while (s < e) {
      if (s % 2 == 1) ret = min(ret, tquery(tree[s++], x));
      if (e % 2 == 0) ret = min(ret, tquery(tree[e--], x));
      s >>= 1;
      e >>= 1;
    }
    if (s == e) ret = min(ret, tquery(tree[s], x));
    return ret;
  }
} seg;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    s[i] = a[i] + s[i - 1];
  }
  seg.init();
  int q;
  scanf("%d", &q);
  while (q--) {
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%lld\n", seg.query(y - x + 1, y, x - y) + s[y]);
  }
}
