#include <bits/stdc++.h>
using namespace std;
const long long is_query = -(1LL << 62);
struct line {
  long long m, b;
  mutable function<const line*()> succ;
  bool operator<(const line& rhs) const {
    if (rhs.b != is_query) return m < rhs.m;
    const line* s = succ();
    if (!s) return 0;
    long long x = rhs.m;
    return b - s->b < (s->m - m) * x;
  }
};
struct dynamic_hull : public multiset<line> {
  const long long inf = LLONG_MAX;
  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;
    long long v1 = (x->b - y->b);
    if (y->m == x->m)
      v1 = x->b > y->b ? inf : -inf;
    else
      v1 /= (y->m - x->m);
    long long v2 = (y->b - z->b);
    if (z->m == y->m)
      v2 = y->b > z->b ? inf : -inf;
    else
      v2 /= (z->m - y->m);
    return v1 >= v2;
  }
  void insert_line(long long m, long long b) {
    auto y = insert({m, b});
    y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
    if (bad(y)) {
      erase(y);
      return;
    }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
  }
  long long eval(long long x) {
    auto l = *lower_bound(line{x, is_query});
    return l.m * x + l.b;
  }
};
struct SegmentTree {
  vector<dynamic_hull> data;
  int size;
  SegmentTree(int size, const vector<int>& a, const vector<int>& pref)
      : size(size), data(4 * size) {
    build(0, 0, size, a, pref);
  }
  void build(int curr, int left, int right, const vector<int>& a,
             const vector<int>& pref) {
    for (int j = left; j < right; ++j) {
      data[curr].insert_line(-a[j], pref[j] - 1LL * a[j] * j);
    }
    if (right - left > 1) {
      int mid = (left + right) / 2;
      build(2 * curr + 1, left, mid, a, pref);
      build(2 * curr + 2, mid, right, a, pref);
    }
  }
  long long query(int i, int j) {
    return query(j - i + 1, j + 1, 0, 0, size, i - j);
  }
  long long query(int leftq, int rightq, int curr, int left, int right, int x) {
    if (leftq >= right || rightq <= left) {
      return 1e18;
    } else if (leftq <= left && right <= rightq) {
      return -data[curr].eval(x);
    }
    int mid = (left + right) / 2;
    return min(query(leftq, rightq, 2 * curr + 1, left, mid, x),
               query(leftq, rightq, 2 * curr + 2, mid, right, x));
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(1 + n, 0), pref(1 + n, 0);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pref[i] = pref[i - 1] + a[i];
  }
  SegmentTree sq(n + 1, a, pref);
  int m;
  cin >> m;
  for (int _ = 0; _ < m; ++_) {
    int x, y;
    cin >> x >> y;
    cout << sq.query(x, y) + pref[y] << "\n";
  }
  return 0;
}
