#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, w, h, k1, res, l, r, k, m, p[N], a[N];
vector<pair<int, int> > t[4 * N], kek;
pair<int, int> b[N];
long double intersectional(pair<int, int> a, pair<int, int> b) {
  return 1.0 * (b.second - a.second) / (a.first - b.first);
}
int len;
bool cmp(pair<int, int> l1, pair<int, int> l2) {
  return l1.first < l2.first || (l1.first == l2.first && l1.second < l2.second);
}
void add(vector<pair<int, int> > &v, pair<int, int> t) {
  if (len < 2) {
    v.push_back(t);
    len++;
  } else {
    long double p1 = intersectional(v[len - 2], t);
    bool ok = (p1 * v[len - 1].first + v[len - 1].second <=
               p1 * v[len - 2].first + v[len - 2].second);
    while (ok && len >= 2) {
      len--;
      v.pop_back();
      p1 = intersectional(v[len - 2], t);
      ok = (p1 * v[len - 1].first + v[len - 1].second <=
            p1 * v[len - 2].first + v[len - 2].second);
    }
    v.push_back(t);
    len++;
  }
}
int get(int v, int l, int r, int tl, int tr, int ll, int rr) {
  if (tl <= l && r <= tr) {
    int l1 = 0, r1 = t[v].size() - 1;
    while (l1 < r1) {
      int m1 = (l1 + r1) >> 1;
      int k1 = t[v][m1].first, b1 = t[v][m1].second;
      int k2 = t[v][m1 + 1].first, b2 = t[v][m1 + 1].second;
      if (k1 * (ll - rr) + b1 <= k2 * (ll - rr) + b2)
        l1 = m1 + 1;
      else
        r1 = m1;
    }
    int k1 = t[v][l1].first, b1 = t[v][l1].second;
    return k1 * (ll - rr) + b1;
  }
  if (l > tr || r < tl) return 0;
  int m = (l + r) >> 1;
  return max(get((v << 1), l, m, tl, tr, ll, rr),
             get((v << 1) + 1, m + 1, r, tl, tr, ll, rr));
}
void build(int v, int l, int r) {
  if (l == r)
    t[v].push_back(b[l]);
  else {
    int m = (l + r) >> 1;
    build((v << 1), l, m);
    build((v << 1) + 1, m + 1, r);
    len = 0;
    vector<pair<int, int> > ans;
    ans.resize(t[v + v].size() + t[v + v + 1].size());
    merge(t[v + v].begin(), t[v + v].end(), t[v + v + 1].begin(),
          t[v + v + 1].end(), ans.begin(), cmp);
    for (int i = 0; i < ans.size(); i++) add(t[v], ans[i]);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[i] = p[i - 1] + a[i];
    b[i] = {-a[i], p[i] - a[i] * i};
  }
  build(1, 1, n);
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> l >> r;
    int resv = get(1, 1, n, r - l + 1, r, l, r);
    cout << p[r] - resv << "\n";
  }
}
