#include <bits/stdc++.h>
using namespace std;
const int oo = 1e9 + 1;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
long long n, a[maxn], m, x, y, sum[maxn], b[maxn], res;
struct Line {
  long double a;
  long double b;
};
vector<pair<Line, long double> > Convex[4 * maxn];
bool TurnLeft(Line L1, Line L2, Line L3) {
  return (L3.b - L1.b) * 1.0 / (L1.a - L3.a) <
         (L2.b - L1.b) * 1.0 / (L1.a - L2.a);
}
void Update(int id, int l, int r, int u, long double a, long double b) {
  if (u < l || u > r) return;
  if (l <= u && u <= r) {
    while ((int)Convex[id].size() >= 1 &&
           Convex[id][Convex[id].size() - 1].first.a == a)
      Convex[id].pop_back();
    while ((int)Convex[id].size() >= 2 &&
           TurnLeft(Convex[id][Convex[id].size() - 2].first,
                    Convex[id][Convex[id].size() - 1].first, Line{a, b}))
      Convex[id].pop_back();
    Convex[id].push_back({Line{a, b}, +oo});
    if ((int)Convex[id].size() >= 2)
      Convex[id][Convex[id].size() - 2].second =
          (b - Convex[id][Convex[id].size() - 2].first.b) /
          (Convex[id][Convex[id].size() - 2].first.a - a);
    if (l == r) return;
  }
  int mid = (l + r) / 2;
  Update(id * 2, l, mid, u, a, b);
  Update(id * 2 + 1, mid + 1, r, u, a, b);
}
void Init() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    b[i] = i;
    sum[i] = sum[i - 1] + a[i];
  }
  sort(b + 1, b + n + 1, [](int x, int y) {
    return (a[x] > a[y] || (a[x] == a[y] && sum[x] < sum[y]));
  });
  for (int i = 1; i <= n; ++i)
    Update(1, 1, n, b[i], a[b[i]], a[b[i]] * b[i] - sum[b[i]]);
}
bool cmp(pair<Line, long double> a, pair<Line, long double> b) {
  return a.second < b.second;
}
void Query(int id, int l, int r, int u, int t) {
  if (u > r || l > t) return;
  if (u <= l && r <= t) {
    int k = lower_bound(Convex[id].begin(), Convex[id].end(),
                        make_pair(Line{0, 0}, x - y), cmp) -
            Convex[id].begin();
    res = min((long double)res,
              Convex[id][k].first.a * (x - y) + Convex[id][k].first.b);
    return;
  }
  int mid = (l + r) / 2;
  Query(id * 2, l, mid, u, t);
  Query(id * 2 + 1, mid + 1, r, u, t);
}
void Solve() {
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> x >> y;
    res = +oo;
    Query(1, 1, n, y - x + 1, y);
    cout << res + sum[y] << '\n';
  }
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  Init();
  Solve();
}
