#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long inf = 1e15;
int a[N], s[N];
struct node {
  long long k, b;
  friend bool operator<(node A, node B) {
    if (A.k == B.k) return A.b > B.b;
    return A.k > B.k;
  }
};
long long ans, nw;
vector<node> v[N << 2], sta;
vector<node>::iterator it;
int top, n, m;
double cro(node A, node B) {
  if (A.k == B.k) return -inf;
  return (B.b - A.b) / (double)(A.k - B.k);
}
long long calc(node A, long long B) { return A.k * B + A.b; }
void pop_() {
  it = sta.end();
  it--;
  sta.erase(it);
  top--;
}
void build(int k, int l, int r) {
  for (register int i = (l); i <= (r); ++i)
    v[k].push_back((node){a[i], 1ll * i * a[i] - s[i]});
  sort(v[k].begin(), v[k].end());
  for (register int i = (0); i <= ((int)(v[k].size()) - 1); ++i) {
    while (top > 1 &&
           cro(sta[top - 2], sta[top - 1]) >= cro(sta[top - 1], v[k][i]))
      pop_();
    sta.push_back(v[k][i]);
    top++;
  }
  v[k] = sta;
  sta.clear();
  top = 0;
  if (l == r) return;
  int mid = l + r >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
}
void query(int k, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    ans = min(ans, calc(v[k][0], nw));
    if (v[k].size() > 1) {
      int tl = 1, tr = v[k].size(), tmid;
      tr--;
      while (tl <= tr) {
        tmid = tl + tr >> 1;
        ans = min(ans, calc(v[k][tmid], nw));
        if (cro(v[k][tmid - 1], v[k][tmid]) <= nw)
          tl = tmid + 1;
        else
          tr = tmid - 1;
      }
    }
    return;
  }
  int mid = l + r >> 1;
  if (x <= mid) query(k << 1, l, mid, x, y);
  if (mid < y) query(k << 1 | 1, mid + 1, r, x, y);
  return;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (register int i = (1); i <= (n); ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
  build(1, 1, n);
  int x, y;
  cin >> m;
  for (register int i = (1); i <= (m); ++i) {
    cin >> x >> y;
    ans = inf;
    nw = x - y;
    query(1, 1, n, max(1, y - x), y);
    cout << ans + s[y] << '\n';
  }
  return 0;
}
