#include <bits/stdc++.h>
using namespace std;
struct node {
  double x, y;
  bool operator<(const node &A) const {
    if (x == A.x) return y < A.y;
    return x < A.x;
  }
} N[300010];
double inf = 1e10;
int a[100010], s[100010], n, m, x, y;
inline node make(double x, double y) {
  node ans;
  ans.x = x;
  ans.y = y;
  return ans;
}
double Gety(node L, node R, double x) {
  if (L.x == x) return L.y;
  if (R.x == x) return R.y;
  double K = (R.y - L.y) / (R.x - L.x);
  double B = L.y - K * L.x;
  return K * x + B;
}
double cp(node A, node B, node C) {
  double x1 = B.x - A.x, x2 = C.x - A.x, y1 = B.y - A.y, y2 = C.y - A.y;
  return x1 * y2 - x2 * y1;
}
bool Xjiao(node A, node B, node C, node D) {
  return (cp(C, A, B) * cp(D, A, B) < 0);
}
double jiao(node A, node B, node C, node D) {
  double s1 = cp(C, A, D), s2 = cp(C, D, B);
  return s1 * B.x / (s1 + s2) + s2 * A.x / (s1 + s2);
}
double tmp[300010], Y[300010];
double Abs(double x) {
  if (x < 0) return -x;
  return x;
}
struct seg {
  vector<node> tr[400010];
  double Find(int p, double x) {
    int t =
        upper_bound(tr[p].begin(), tr[p].end(), make(x, -inf)) - tr[p].begin();
    if (t) return Gety(tr[p][t - 1], tr[p][t], x);
    return Gety(tr[p][t], tr[p][t + 1], x);
  }
  void updata(int p) {
    int tot = 0, now = 0;
    for (int i = 0; i < (int)tr[(p << 1)].size(); i++)
      tmp[++tot] = tr[(p << 1)][i].x;
    for (int i = 0; i < (int)tr[((p << 1) + 1)].size(); i++)
      tmp[++tot] = tr[((p << 1) + 1)][i].x;
    for (int i = 0; i < (int)tr[(p << 1)].size() - 1; i++) {
      int j = now;
      for (; now < (int)tr[((p << 1) + 1)].size() - 1 &&
             tr[((p << 1) + 1)][now + 1].x < tr[(p << 1)][i + 1].x;
           now++)
        ;
      for (int k = j; k <= now && k + 1 < tr[((p << 1) + 1)].size(); k++)
        if (Xjiao(tr[(p << 1)][i], tr[(p << 1)][i + 1], tr[((p << 1) + 1)][k],
                  tr[((p << 1) + 1)][k + 1]))
          tmp[++tot] = jiao(tr[(p << 1)][i], tr[(p << 1)][i + 1],
                            tr[((p << 1) + 1)][k], tr[((p << 1) + 1)][k + 1]);
    }
    sort(tmp + 1, tmp + tot + 1);
    tot = unique(tmp + 1, tmp + tot + 1) - (tmp + 1);
    for (int i = 1; i <= tot; i++)
      Y[i] = min(Find((p << 1), tmp[i]), Find(((p << 1) + 1), tmp[i]));
    int top = 0;
    for (int i = 1; i <= tot; i++) {
      node t = make(tmp[i], Y[i]);
      while (top > 1 && Abs(cp(N[top - 1], N[top], t)) <= 1e-7) top--;
      N[++top] = t;
    }
    for (int i = 1; i <= top; i++) tr[p].push_back(N[i]);
  }
  void Build(int p, int l, int r) {
    if (l == r - 1) {
      tr[p].push_back(make(0, a[l] * l - s[l]));
      tr[p].push_back(make(n, (l - n) * a[l] - s[l]));
      return;
    }
    Build((p << 1), l, ((l + r) >> 1));
    Build(((p << 1) + 1), ((l + r) >> 1), r);
    updata(p);
  }
  double Getans(int p, int l, int r, int a, int b, int x) {
    if (l == a && r == b) return Find(p, x);
    if (b <= ((l + r) >> 1))
      return Getans((p << 1), l, ((l + r) >> 1), a, b, x);
    if (a >= ((l + r) >> 1))
      return Getans(((p << 1) + 1), ((l + r) >> 1), r, a, b, x);
    return min(Getans((p << 1), l, ((l + r) >> 1), a, ((l + r) >> 1), x),
               Getans(((p << 1) + 1), ((l + r) >> 1), r, ((l + r) >> 1), b, x));
  }
} T;
void read(int &x) {
  char ch = getchar();
  int mark = 1;
  for (; ch != '-' && (ch < '0' || ch > '9'); ch = getchar())
    ;
  if (ch == '-') mark = -1, ch = getchar();
  for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
  x *= mark;
}
int main() {
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
  T.Build(1, 1, n + 1);
  read(m);
  for (; m--;) {
    read(x);
    read(y);
    printf("%.0lf\n",
           Abs(T.Getans(1, 1, n + 1, y - x + 1, y + 1, y - x) + s[y]));
  }
  return 0;
}
