#include <bits/stdc++.h>
using namespace std;
int n, a[500005], m, A, ll, rr, ans, sum[500005], cnt, ccc;
struct point {
  int x, y;
} E[500005], stk[500005], tmp[500005];
bool cmp(const point &i, const point &j) {
  return i.x == j.x ? i.y < j.y : i.x < j.x;
}
vector<point> tree[500005];
long long chaji(const point &i, const point &j, const point &k) {
  long long x0, y0, x1, y1;
  x0 = j.x - k.x;
  y0 = j.y - k.y;
  x1 = i.x - k.x;
  y1 = i.y - k.y;
  return y0 * x1 - x0 * y1;
}
void build(int t, int l, int r) {
  for (int i = l; i <= r; i++) tmp[i] = E[i];
  sort(tmp + l, tmp + 1 + r, cmp);
  int top = 0;
  for (int i = l; i <= r; i++) {
    while (top > 1 && chaji(tmp[i], stk[top], stk[top - 1]) >= 0) top--;
    stk[++top] = tmp[i];
  }
  cnt += 1;
  for (int i = 1; i <= top; i++) tree[t].push_back(stk[i]);
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(t * 2, l, mid);
  build(t * 2 + 1, mid + 1, r);
}
int calc(const point &t) { return A * t.x + t.y; }
void query(int t, int l, int r) {
  if (ll <= l && r <= rr) {
    int L = 0, R = tree[t].size() - 1;
    while (R - L > 2) {
      int s1 = L + (R - L) / 3, s2 = L + (R - L) / 3 * 2;
      if (calc(tree[t][s1]) > calc(tree[t][s2]))
        L = s1 + 1;
      else
        R = s2 - 1;
      cnt++;
    }
    for (int i = L; i <= R; i++)
      if (calc(tree[t][i]) < ans) ans = calc(tree[t][i]);
    return;
  }
  int mid = (l + r) >> 1;
  if (ll <= mid) query(t * 2, l, mid);
  if (rr > mid) query(t * 2 + 1, mid + 1, r);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
  for (int i = 1; i <= n; i++) E[i].x = a[i], E[i].y = i * a[i] - sum[i];
  build(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    int i, j;
    scanf("%d%d", &i, &j);
    ll = j - i + 1;
    rr = j;
    ans = 0x7f7f7f7f;
    A = i - j;
    query(1, 1, n);
    printf("%d\n", ans + sum[j]);
  }
}
