#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
const long long inf = 1LL << 60;
long long read() {
  long long s = 0;
  char c = getchar(), lc = '+';
  while (c < '0' || '9' < c) lc = c, c = getchar();
  while ('0' <= c && c <= '9') s = s * 10 + c - '0', c = getchar();
  return lc == '-' ? -s : s;
}
void write(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x < 10)
    putchar(x + '0');
  else {
    write(x / 10);
    putchar(x % 10 + '0');
  }
}
void print(long long x, char c = '\n') {
  write(x);
  putchar(c);
}
struct LiChao_Tree {
  pair<long long, long long> st[N * 22];
  long long top;
  long long k[N], b[N], cntl;
  struct node {
    long long v, ls, rs;
  } t[N * 22];
  long long cntn, root;
  bool cmp(long long u, long long v, long long x) {
    return k[u] * x + b[u] < k[v] * x + b[v];
  }
  void insert(long long &w, long long l, long long r, long long x) {
    if (!w) w = ++cntn;
    if (cmp(x, t[w].v, ((l + r) / 2)))
      st[++top] = make_pair(w, t[w].v), swap(t[w].v, x);
    if (l == r) return;
    if (cmp(x, t[w].v, l)) insert(t[w].ls, l, ((l + r) / 2), x);
    if (cmp(x, t[w].v, r)) insert(t[w].rs, ((l + r) / 2) + 1, r, x);
  }
  void insert(long long _k, long long _b) {
    cntl++;
    k[cntl] = _k;
    b[cntl] = _b;
    insert(root, -5e5, 1e9, cntl);
  }
  long long query(long long w, long long l, long long r, long long x) {
    if (!w) return inf;
    long long ret = k[t[w].v] * x + b[t[w].v];
    if (l == r) return ret;
    if (x <= ((l + r) / 2))
      return min(ret, query(t[w].ls, l, ((l + r) / 2), x));
    else
      return min(ret, query(t[w].rs, ((l + r) / 2) + 1, r, x));
  }
  void pop(long long x) {
    while (top > x) t[st[top].first].v = st[top].second, top--;
  }
} t;
vector<pair<long long, long long> > q[N];
long long a[N], st[N], top = 0, Top[N], ans[N], sum[N];
signed main() {
  long long n = read();
  for (long long i = 1; i <= n; i++) sum[i] = sum[i - 1] + (a[i] = read());
  long long Q = read();
  for (long long i = 1; i <= Q; i++) {
    long long x = read(), y = read();
    q[y].push_back(make_pair(x, i));
  }
  for (long long i = 1; i <= n; i++) {
    while (top && a[st[top]] >= a[i]) top--;
    t.pop(Top[top]);
    st[++top] = i;
    t.insert(a[i], a[i] * i - sum[i]);
    Top[top] = t.top;
    for (auto j : q[i]) {
      long long x = j.first;
      ans[j.second] = t.query(t.root, -5e5, 1e9, x - i) + sum[i];
    }
  }
  for (long long i = 1; i <= Q; i++) print(ans[i]);
  return 0;
}
