#include <bits/stdc++.h>
using namespace std;
template <typename G1, typename G2 = G1, typename G3 = G1>
struct triple {
  G1 first;
  G2 second;
  G3 T;
};
template <typename T>
T cross(complex<T> a, complex<T> b) {
  return imag(conj(a) * b);
}
template <typename T>
T dot(complex<T> a, complex<T> b) {
  return real(conj(a) * b);
}
struct __Query {
  static bool query;
};
bool __Query::query = false;
template <typename T>
struct Point {
  complex<T> p;
  mutable function<const complex<T> *()> succ;
  bool operator<(const Point &rhs) const {
    const complex<T> &q = rhs.p;
    if (!__Query::query) {
      if (real(p) != real(q)) return real(p) < real(q);
      return imag(p) < imag(q);
    }
    const complex<T> *s = succ();
    if (!s) return false;
    return dot(p - *s, q) < 0;
  }
};
template <typename T, int turn>
struct half_hull : public set<Point<T>> {
  using set<Point<T>>::begin;
  using set<Point<T>>::insert;
  using set<Point<T>>::end;
  using set<Point<T>>::lower_bound;
  using set<Point<T>>::empty;
  using set<Point<T>>::erase;
  using typename set<Point<T>>::iterator;
  complex<T> extreme(const complex<T> &p) const {
    assert(!empty() && turn * imag(p) >= 0);
    __Query::query = true;
    auto pos = lower_bound(Point<T>{p});
    __Query::query = false;
    assert(pos != end());
    return pos->p;
  }
  void insert(const complex<T> &p) {
    auto y = insert(Point<T>{p}).first;
    if (y == end()) return;
    y->succ = [=] { return next(y) == end() ? nullptr : &next(y)->p; };
    if (bad(y)) {
      erase(y);
      return;
    }
    while (y != begin() && bad(prev(y))) erase(prev(y));
    while (next(y) != end() && bad(next(y))) erase(next(y));
  }

 private:
  bool bad(iterator y) {
    if (y == begin() || y == end()) return false;
    auto x = prev(y), z = next(y);
    if (z == end()) return false;
    return cross(y->p - x->p, z->p - x->p) * turn >= 0;
  }
};
template <typename T>
struct convex_hull_trick {
  void insert(const complex<T> &p) {
    lower_hull.insert(p);
    upper_hull.insert(p);
  }
  complex<T> extreme(const complex<T> &p) const {
    if (std::imag(p) < 0) return lower_hull.extreme(p);
    return upper_hull.extreme(p);
  }

 private:
  half_hull<T, +1> upper_hull;
  half_hull<T, -1> lower_hull;
};
struct segment_tree {
  vector<convex_hull_trick<long long>> st;
  const int oo = 2e9;
  segment_tree(int n, vector<complex<long long>> &lines) : st(2 * n) {
    build(0, n, lines);
  }
  inline int id(int b, int e) { return (b + e - 1) | (b != e - 1); }
  void build(int l, int r, vector<complex<long long>> &lines) {
    int cur = id(l, r);
    for (int i = l; i < r; i++) st[cur].insert(-lines[i]);
    if (r == l + 1) return;
    int mid = (l + r + 1) >> 1;
    build(l, mid, lines);
    build(mid, r, lines);
  }
  long long query(int l, int r, int li, int ri, complex<long long> p) {
    int cur = id(l, r);
    if (l >= ri || r <= li) return oo;
    if (li <= l && r <= ri) return -dot(st[cur].extreme(p), {p.real(), 1});
    int mid = (l + r + 1) >> 1;
    return min(query(l, mid, li, ri, p), query(mid, r, li, ri, p));
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> v(n);
  for (auto &i : v) cin >> i;
  vector<long long> a(n + 1);
  for (int i = 1; i <= n; i++) a[i] = a[i - 1] + v[i - 1];
  vector<complex<long long>> l(n);
  for (int i = 1; i <= n; i++) l[i - 1] = {v[i - 1], v[i - 1] * i - a[i]};
  segment_tree st(n, l);
  int m;
  cin >> m;
  while (m--) {
    int x, y;
    cin >> x >> y;
    --y;
    cout << st.query(0, n, y - x + 1, y + 1, complex<long long>{x - y - 1, 1}) +
                a[y + 1]
         << '\n';
  }
  return 0;
}
