#include <bits/stdc++.h>
using namespace std;
template <class T, class L>
inline bool smax(T &x, L y) {
  return x < y ? (x = y, 1) : 0;
}
template <class T, class L>
inline bool smin(T &x, L y) {
  return y < x ? (x = y, 1) : 0;
}
const int maxn = 1e5 + 17;
const long long inf = 1e18;
int n, q, a[maxn], ptr[maxn], ps[maxn];
long long b[maxn];
inline long long f(int i, int x) { return (long long)a[i] * x + b[i]; }
vector<pair<int, int> > iman[maxn << 2];
int when(int i, int j) {
  int ans = (b[j] - b[i]) / (a[i] - a[j]);
  if (f(i, ans) < f(j, ans)) return ans;
  return ans + 1;
}
void majid(int l = 0, int r = n, int id = 1) {
  if (r - l < 2) {
    iman[id].push_back({-maxn, l});
    return;
  }
  int mid = l + r >> 1;
  majid(l, mid, id << 1), majid(mid, r, id << 1 | 1);
  vector<pair<int, int> > &v = iman[id];
  int sz = 0;
  for (auto &x : iman[id << 1]) ptr[sz++] = x.second;
  for (auto &x : iman[id << 1 | 1]) ptr[sz++] = x.second;
  sort(ptr, ptr + sz, [](int &i, int &j) { return f(i, -maxn) < f(j, -maxn); });
  v.push_back({-maxn, ptr[0]});
  for_each(ptr + 1, ptr + sz, [&](int &i) {
    while (v.size() > 1 && a[i] < a[v.back().second] &&
           when(i, v.back().second) <= v.back().first)
      v.pop_back();
    if (a[i] < a[v.back().second]) v.push_back({when(i, v.back().second), i});
  });
}
long long hamid(int s, int e, int x, int l = 0, int r = n, int id = 1) {
  if (s <= l && r <= e)
    return f((--lower_bound(iman[id].begin(), iman[id].end(),
                            pair<int, int>(x, maxn)))
                 ->second,
             x);
  if (e <= l || r <= s) return inf;
  int mid = l + r >> 1;
  return min(hamid(s, e, x, l, mid, id << 1),
             hamid(s, e, x, mid, r, id << 1 | 1));
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  partial_sum(a, a + n, ps);
  for (int i = 0; i < n; i++) b[i] = (long long)a[i] * (i + 1) - ps[i];
  majid();
  cin >> q;
  for (int x, y; q--;) {
    cin >> x >> y, y--;
    cout << hamid(y - x + 1, y + 1, x - y - 1) + ps[y] << '\n';
  }
  return 0;
}
