#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 262250;
int n, m, a[N], sum[N], now, T[M], Y1[M], Y2[M], A[N], B[N], visit[M], X[N],
    Y[N], Ans[N];
vector<int> h[M];
char c, S[12];
int read() {
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    ;
  int x = c - 48;
  for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x;
}
void Add(int l, int r, int a, int b, int v, int x) {
  if (l == a && r == b) {
    h[x].push_back(v);
    return;
  }
  int mid = l + r >> 1;
  if (b <= mid)
    Add(l, mid, a, b, v, x << 1);
  else if (a > mid)
    Add(mid + 1, r, a, b, v, x << 1 | 1);
  else {
    Add(l, mid, a, mid, v, x << 1);
    Add(mid + 1, r, mid + 1, b, v, x << 1 | 1);
  }
}
void Ins(int l, int r, int v, int x) {
  if (visit[x] != now) {
    visit[x] = now;
    if (l == r)
      T[x] = A[v] * l + B[v];
    else {
      T[x] = v;
      Y1[x] = A[v] * l + B[v];
      Y2[x] = A[v] * r + B[v];
    }
    return;
  }
  if (l == r) {
    T[x] = ((T[x]) < (A[v] * l + B[v]) ? (T[x]) : (A[v] * l + B[v]));
    return;
  }
  int y1 = A[v] * l + B[v], y2 = A[v] * r + B[v];
  if (y1 >= Y1[x] && y2 >= Y2[x]) return;
  if (y1 <= Y1[x] && y2 <= Y2[x]) {
    Y1[x] = y1;
    Y2[x] = y2;
    T[x] = v;
    return;
  }
  int mid = l + r >> 1;
  if (A[v] * mid + B[v] > A[T[x]] * mid + B[T[x]]) {
    if (y1 < Y1[x])
      Ins(l, mid, v, x << 1);
    else
      Ins(mid + 1, r, v, x << 1 | 1);
  } else {
    if (y1 < Y1[x])
      Ins(mid + 1, r, T[x], x << 1 | 1);
    else
      Ins(l, mid, T[x], x << 1);
    T[x] = v;
    Y1[x] = y1;
    Y2[x] = y2;
  }
}
void query(int l, int r, int v, int id, int x) {
  if (visit[x] != now) return;
  if (l == r) {
    Ans[id] = ((Ans[id]) < (T[x]) ? (Ans[id]) : (T[x]));
    return;
  }
  int mid = l + r >> 1;
  if (v <= mid)
    query(l, mid, v, id, x << 1);
  else
    query(mid + 1, r, v, id, x << 1 | 1);
  Ans[id] = ((Ans[id]) < (A[T[x]] * v + B[T[x]]) ? (Ans[id])
                                                 : (A[T[x]] * v + B[T[x]]));
}
void solve(int l, int r, int x) {
  if (l < r) {
    int mid = l + r >> 1;
    solve(l, mid, x << 1);
    solve(mid + 1, r, x << 1 | 1);
  }
  if (h[x].empty()) return;
  now = x;
  for (int i = l; i <= r; i++) Ins(0, n, i, 1);
  vector<int>::iterator it;
  for (it = h[x].begin(); it != h[x].end(); it++)
    query(0, n, Y[*it] - X[*it], *it, 1);
}
void write(int x) {
  if (x == 0) {
    putchar('0');
    putchar('\n');
    return;
  }
  int len = 0;
  for (; x > 0; x /= 10) S[len++] = x % 10;
  for (int i = len - 1; i >= 0; i--) putchar(S[i] + '0');
  putchar('\n');
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    sum[i] = sum[i - 1] + a[i];
    A[i] = -a[i];
    B[i] = i * a[i] - sum[i];
  }
  m = read();
  for (int i = 0; i < m; i++) {
    X[i] = read();
    Y[i] = read();
    Ans[i] = -1e9;
    Add(1, n, Y[i] - X[i] + 1, Y[i], i, 1);
  }
  memset(Y1, 127, sizeof(Y1));
  memset(Y2, 127, sizeof(Y2));
  memset(Ans, 127, sizeof(Ans));
  solve(1, n, 1);
  for (int i = 0; i < m; i++) write(Ans[i] + sum[Y[i]]);
  return 0;
}
