#include <bits/stdc++.h>
using namespace std;
unsigned next_unsigned() {
  char c;
  unsigned i;
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    ;
  for (i = c - '0', c = getchar(); c >= '0' && c <= '9';
       i = i * 10 + c - '0', c = getchar())
    ;
  return i;
}
int next_int() {
  char c;
  int i;
  bool neg = false;
  for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar())
    ;
  if (c == '-') neg = true, c = getchar();
  for (i = c - '0', c = getchar(); c >= '0' && c <= '9';
       i = i * 10 + c - '0', c = getchar())
    ;
  return neg ? -i : i;
}
struct Line {
  int k, b;
  Line(int k = 0, int b = 0) : k(k), b(b) {}
} po[101000];
const long double eps = 1e-9;
long double sgn(long double x) { return x > eps ? 1 : x < -eps ? -1 : 0; }
long double sgn(long double a, long double b) { return sgn(a - b); }
int n;
vector<Line> t[101000 << 2];
long double intersect_x(const Line& a, const Line& b) {
  assert(a.k != b.k);
  return (long double)(a.b - b.b) / (b.k - a.k);
}
long long calc(const vector<Line>& a, int x) {
  assert(!a.empty());
  int size = a.size();
  int l = 0, r = size - 1;
  for (; l < r;) {
    int mid = (l + r) / 2;
    if (mid == r || intersect_x(a[mid], a[mid + 1]) > x)
      r = mid;
    else
      l = mid + 1;
  }
  return 1ll * a[l].k * x + a[l].b;
}
void build(int x, int l, int r) {
  if (l == r) {
    t[x].push_back(po[l]);
    return;
  }
  int mid = (l + r) / 2;
  build(((x) << 1), l, mid);
  build(((x) << 1 | 1), mid + 1, r);
  vector<Line> c;
  vector<Line>& s = t[x];
  for (Line l : t[((x) << 1)]) c.push_back(l);
  for (Line l : t[((x) << 1 | 1)]) c.push_back(l);
  sort(c.begin(), c.end(),
       [](Line a, Line b) { return a.k != b.k ? a.k > b.k : a.b < b.b; });
  for (Line l : c) {
    if (!s.empty() && s.back().k == l.k) continue;
    while (s.size() >= 2) {
      int top = s.size();
      if (intersect_x(s[top - 2], s[top - 1]) >= intersect_x(s[top - 2], l))
        s.pop_back();
      else
        break;
    }
    s.push_back(l);
  }
}
long long seg_query(int x, int l, int r, int ql, int qr, int x0) {
  if (ql <= l && r <= qr) {
    return calc(t[x], x0);
  }
  int mid = (l + r) / 2;
  return qr <= mid  ? seg_query(((x) << 1), l, mid, ql, qr, x0)
         : ql > mid ? seg_query(((x) << 1 | 1), mid + 1, r, ql, qr, x0)
                    : min(seg_query(((x) << 1), l, mid, ql, qr, x0),
                          seg_query(((x) << 1 | 1), mid + 1, r, ql, qr, x0));
}
int a[101000];
long long sum[101000];
int main() {
  n = next_int();
  for (int i = 1; i <= n; ++i) {
    a[i] = next_int();
  }
  for (int i = n; i >= 1; --i) {
    sum[i] = sum[i + 1] + a[i];
    po[i] = Line(a[i], sum[i] - (n - i) * a[i]);
  }
  build(1, 1, n);
  int m = next_int();
  for (int i = 1; i <= m; ++i) {
    int x = next_int(), y = next_int();
    printf("%lld\n",
           seg_query(1, 1, n, y - x + 1, y, n - (y - x + 1)) - sum[y + 1]);
  }
  return 0;
}
