#include <bits/stdc++.h>
using namespace std;
struct node {
  int a, b;
  node(int a = 0, int b = (int)1e9) : a(a), b(b) {}
  int get(int x) { return a * x + b; }
};
struct Zwei {
  vector<node> st;
  vector<int> a;
  int n;
  void add(int pos) { a.push_back(pos); }
  void update() {
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    n = (int)a.size();
    st.resize(n << 2 | 1);
  }
  void modify(int id, int l, int r, node val) {
    int mid = l + r >> 1;
    if (st[id].get(a[mid]) > val.get(a[mid])) swap(st[id], val);
    if (l == r) return;
    if (st[id].get(a[l]) > val.get(a[l])) modify(id << 1, l, mid, val);
    if (st[id].get(a[r]) > val.get(a[r])) modify(id << 1 | 1, mid + 1, r, val);
  }
  int get(int id, int l, int r, int v) {
    int ans = st[id].get(v);
    if (l == r) assert(a[l] == v);
    if (l == r) return ans;
    int mid = l + r >> 1;
    if (v <= a[mid]) return min(ans, get(id << 1, l, mid, v));
    return min(ans, get(id << 1 | 1, mid + 1, r, v));
  }
  int get(int v) {
    if (!n) return (int)1e9;
    return get(1, 0, n - 1, v);
  }
  void modify(node val) {
    if (!n) return;
    modify(1, 0, n - 1, val);
  }
};
struct Eins {
  vector<Zwei> st;
  int n;
  Eins(int n) : n(n) { st.resize(n << 2 | 1); }
  void build(int id, int l, int r) {
    st[id].update();
    if (l == r) return;
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
  }
  void add(int id, int l, int r, int L, int R, int v) {
    if (L <= l && r <= R) {
      st[id].add(v);
      return;
    }
    int mid = l + r >> 1;
    if (L <= mid) add(id << 1, l, mid, L, R, v);
    if (R > mid) add(id << 1 | 1, mid + 1, r, L, R, v);
  }
  void modify(int id, int l, int r, int pos, node val) {
    st[id].modify(val);
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid)
      modify(id << 1, l, mid, pos, val);
    else
      modify(id << 1 | 1, mid + 1, r, pos, val);
  }
  int get(int id, int l, int r, int L, int R, int v) {
    if (L <= l && r <= R) return st[id].get(v);
    int mid = l + r >> 1;
    int ans = (int)1e9 + 1;
    if (L <= mid) ans = min(ans, get(id << 1, l, mid, L, R, v));
    if (R > mid) ans = min(ans, get(id << 1 | 1, mid + 1, r, L, R, v));
    return ans;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  vector<int> t(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    t[i] = t[i - 1] + a[i];
  }
  int q;
  cin >> q;
  vector<pair<int, int>> Query;
  Eins Tree(n);
  while (q--) {
    int x, y;
    cin >> x >> y;
    Query.emplace_back(x, y);
    Tree.add(1, 1, n, y - x + 1, y, y - x);
  }
  Tree.build(1, 1, n);
  for (int i = 1; i <= n; i++)
    Tree.modify(1, 1, n, i, node(-a[i], a[i] * i - t[i]));
  for (auto& x : Query) {
    cout << Tree.get(1, 1, n, x.second - x.first + 1, x.second,
                     x.second - x.first) +
                t[x.second]
         << "\n";
  }
}
