#include <bits/stdc++.h>
using namespace std;
const int M = 2000005;
const int N = 100005;
int n, Q, nd, a[N], rt[N * 4];
int ls[M], rs[M];
pair<long long, long long> t[M];
long long S[N];
long long F(pair<long long, long long> x, int y) {
  return x.first * y + x.second;
}
void insert(int &k, int l, int r, pair<long long, long long> p) {
  if (!k) return t[k = ++nd] = p, void(0);
  int mid = (l + r) / 2;
  if (F(t[k], mid) > F(p, mid)) swap(t[k], p);
  if (F(t[k], l) > F(p, l)) insert(ls[k], l, mid, p);
  if (F(t[k], r) > F(p, r)) insert(rs[k], mid + 1, r, p);
}
long long ask(int k, int l, int r, int p) {
  if (!k) return 1ll << 60;
  long long ans = F(t[k], p);
  int mid = (l + r) / 2;
  if (p <= mid) ans = min(ans, ask(ls[k], l, mid, p));
  if (p > mid) ans = min(ans, ask(rs[k], mid + 1, r, p));
  return ans;
}
void insert(int k, int l, int r, int p, pair<long long, long long> v) {
  insert(rt[k], 0, 2 * N,
         pair<long long, long long>(v.first, v.second - N * v.first));
  if (l == r) return;
  int mid = (l + r) / 2;
  if (p <= mid)
    insert(k * 2, l, mid, p, v);
  else
    insert(k * 2 + 1, mid + 1, r, p, v);
}
long long ask(int k, int l, int r, int x, int y, int p) {
  if (l == x && r == y) return ask(rt[k], 0, 2 * N, p + N);
  int mid = (l + r) / 2;
  if (y <= mid) return ask(k * 2, l, mid, x, y, p);
  if (x > mid) return ask(k * 2 + 1, mid + 1, r, x, y, p);
  return min(ask(k * 2, l, mid, x, mid, p),
             ask(k * 2 + 1, mid + 1, r, mid + 1, y, p));
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n); i++) scanf("%d", &a[i]);
  for (int i = (int)(1); i <= (int)(n); i++) S[i] = S[i - 1] + a[i];
  for (int i = (int)(1); i <= (int)(n); i++)
    insert(1, 1, n, i,
           pair<long long, long long>(a[i], -S[i] + 1ll * i * a[i]));
  scanf("%d", &Q);
  while (Q--) {
    int k, x;
    scanf("%d%d", &k, &x);
    printf("%lld\n", ask(1, 1, n, x - k + 1, x, k - x) + S[x]);
  }
}
