#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 11;
const long long oo = 1e17 + 123;
int tcases = 1;
int n, m = 0;
long long a[N], b[N], s[N], res[N];
pair<int, int> q[N];
struct Point {
  double x, y;
  Point() { x = y = 0; }
  Point(double _x, double _y) : x(_x), y(y) {}
};
struct line {
  double a, b;
  line() {
    a = 1;
    b = 0;
  }
  line(double _a, double _b) {
    a = _a;
    b = _b;
  }
  long long val(double x) { return (long long)a >= oo ? oo : x * a + b; }
  double getIntersection(line ll) { return (ll.b - b) / (a - ll.a); }
} l0[N];
struct LiChaoTree {
  vector<int> coor;
  vector<int> queries;
  vector<line> f;
  int m;
  void addline(int k, int l, int r, line ll) {
    if (l == r) {
      if (f[k].val(coor[l - 1]) > ll.val(coor[l - 1])) f[k] = ll;
      return;
    }
    int mid = (l + r) >> 1;
    bool sl = ll.val(coor[l - 1]) < f[k].val(coor[l - 1]),
         smid = ll.val(coor[mid] - 1) < f[k].val(coor[mid] - 1);
    if (smid) swap(f[k], ll);
    if (sl == smid) {
      addline(k << 1 | 1, mid + 1, r, ll);
    } else {
      addline(k << 1, l, mid, ll);
    }
  }
  long long cal(int k, int l, int r, long long x) {
    if (coor[l - 1] > x || coor[r - 1] < x) return oo;
    if (l == r) return f[k].val(x);
    long long rr = f[k].val(x);
    int mid = (l + r) >> 1;
    return min(rr, min(cal(k << 1, l, mid, x), cal(k << 1 | 1, mid + 1, r, x)));
  }
  void init(int l, int r) {
    coor.push_back(-n);
    coor.push_back(0);
    for (int i : queries) {
      coor.push_back(q[i].first - q[i].second - 1);
    }
    sort((coor).begin(), (coor).end());
    coor.erase(unique((coor).begin(), (coor).end()), coor.end());
    m = coor.size() - 1;
    f.assign(m * 4 + 11, line(oo, oo));
    for (int i = l; i <= r; ++i) {
      addline(1, 1, m, l0[i]);
    }
  }
  void getMin(int l, int r) {
    init(l, r);
    for (int i : queries) {
      int x = q[i].first, y = q[i].second;
      res[i] = min(res[i], cal(1, 1, m, x - y - 1) + s[y]);
    }
  }
};
struct IT {
  LiChaoTree f[N * 4];
  void insert(int k, int l, int r, int L, int R, int i) {
    if (L > r || l > R) return;
    if (L <= l && r <= R) {
      f[k].queries.push_back(i);
      return;
    }
    int mid = (l + r) >> 1;
    insert(k << 1, l, mid, L, R, i);
    insert(k << 1 | 1, mid + 1, r, L, R, i);
  }
  void getMin(int k, int l, int r) {
    f[k].getMin(l, r);
    if (l < r) {
      int mid = (l + r) >> 1;
      getMin(k << 1, l, mid);
      getMin(k << 1 | 1, mid + 1, r);
    }
  }
} segmentTree;
void testcase() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    s[i] = s[i - 1] + a[i];
    l0[i] = line(a[i], a[i] * i - s[i - 1]);
  }
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    segmentTree.insert(1, 1, n, y - x + 1, y, i);
    q[i] = make_pair(x, y);
  }
  for (int i = 1; i <= m; ++i) res[i] = oo;
  segmentTree.getMin(1, 1, n);
  for (int i = 1; i <= m; ++i) cout << res[i] << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  for (int i = 1; i <= tcases; ++i) testcase();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
