#include <bits/stdc++.h>
using namespace std;
long long bigmod(long long b, long long p) {
  if (p == 0) return 1;
  long long my = bigmod(b, p / 2);
  my *= my;
  my %= 1000000007;
  if (p & 1) my *= b, my %= 1000000007;
  return my;
}
int setb(int n, int pos) { return n = n | (1 << pos); }
int resb(int n, int pos) { return n = n & ~(1 << pos); }
bool checkb(int n, int pos) { return (bool)(n & (1 << pos)); }
long long n, m, ara[100005], sum[100005];
struct line {
  long long m, c, idx;
  line(){};
  line(long long _m, long long _c) {
    m = _m;
    c = _c;
  }
  void _print() { printf("%lld %lld\n", m, c); }
  bool operator<(const line &p) const {
    if (m == p.m)
      return c < p.c;
    else
      return m > p.m;
  }
  bool operator==(const line &p) const {
    if (m == p.m && c == p.c)
      return true;
    else
      return false;
  }
};
stack<line> st;
vector<line> tree[4 * 100005];
line lol[100005];
bool isbad(line l1, line l2, line l3) {
  return 1.0 * (l3.c - l1.c) * (l1.m - l2.m) <
         1.0 * (l2.c - l1.c) * (l1.m - l3.m);
}
void add(long long ind, line L) {
  while (st.size() > 1) {
    line t = st.top();
    st.pop();
    line nxt = st.top();
    if (isbad(nxt, t, L))
      continue;
    else {
      st.push(t);
      break;
    }
  }
  st.push(L);
}
void go(long long ind, long long b, long long e) {
  vector<line> v, tmp;
  for (long long i = b; i <= e; i++) tmp.push_back(lol[i]);
  sort(tmp.begin(), tmp.end());
  line prv = line(-1, -1);
  for (long long i = 0; i < tmp.size(); i++) {
    if (tmp[i].m != prv.m) v.push_back(tmp[i]);
    prv = tmp[i];
  }
  assert(st.empty());
  for (long long i = 0; i < v.size(); i++) add(ind, v[i]);
  while (st.empty() == 0) {
    line t = st.top();
    st.pop();
    tree[ind].push_back(t);
  }
  reverse(tree[ind].begin(), tree[ind].end());
}
void init(long long ind, long long b, long long e) {
  go(ind, b, e);
  if (b == e) return;
  long long mid = (b + e) / 2, l = 2 * ind, r = l + 1;
  init(l, b, mid);
  init(r, mid + 1, e);
}
long long f;
long long Intersection(long long ind, long long idx1, long long idx2) {
  long long val = (tree[ind][idx2].c - tree[ind][idx1].c) /
                  (tree[ind][idx1].m - tree[ind][idx2].m);
  if ((tree[ind][idx2].c - tree[ind][idx1].c) %
      (tree[ind][idx1].m - tree[ind][idx2].m)) {
    f = 1;
    if (val < 0) f = -1;
  } else
    f = 0;
  return val;
}
long long Find(long long ind, long long x) {
  long long len = tree[ind].size();
  long long low = 0, high = len - 1, mid, ans;
  while (low <= high) {
    mid = (low + high) / 2;
    long long my = (long long)1e15;
    if (mid != len - 1) my = Intersection(ind, mid, mid + 1);
    my *= 2;
    my += f;
    if (my >= 2 * x) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  return tree[ind][ans].m * x + tree[ind][ans].c;
}
long long Q(long long ind, long long b, long long e, long long i, long long j,
            long long x) {
  if (i > j) return (long long)1e15;
  if (b == i && e == j) return Find(ind, x);
  long long mid = (b + e) / 2, l = 2 * ind, r = l + 1;
  return min(Q(l, b, mid, i, min(j, mid), x),
             Q(r, mid + 1, e, max(mid + 1, i), j, x));
}
void prework() {
  long long i;
  for (i = 1; i <= n; i++) lol[i] = line(ara[i], i * ara[i] - sum[i]);
  init(1, 1, n);
}
long long F(long long x, long long y) {
  long long l = y - x + 1;
  return sum[y] + Q(1, 1, n, l, y, x - y);
}
int main() {
  long long i, x, y;
  scanf("%lld", &n);
  for (i = 1; i <= n; i++) scanf("%lld", &ara[i]), sum[i] = sum[i - 1] + ara[i];
  prework();
  scanf("%lld", &m);
  for (i = 1; i <= m; i++) {
    scanf("%lld %lld", &x, &y);
    long long ret = F(x, y);
    printf("%lld", ret);
    printf("\n");
  }
  return 0;
}
