#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], c[N];
int ans[N];
struct qq {
  int x, y, id;
} s[N];
int n, Q;
bool cmp(qq x, qq y) { return x.y < y.y; }
int q[N];
int st, ed, now;
double Y(int x) { return a[x] * x - c[x]; }
double X(int x) { return -a[x]; }
double get_k(int x, int y) {
  return (double)(Y(x) - Y(y)) / (double)(X(x) - X(y));
}
int calc(int xx, int x, int y) { return c[y] - c[xx] + a[xx] * (x - y + xx); }
void solve() {
  st = 1;
  ed = 0;
  now = 1;
  for (int u = 1; u <= n; u++) {
    while (st <= ed && a[q[ed]] >= a[u]) ed--;
    while (st < ed && get_k(q[ed - 1], q[ed]) < get_k(q[ed], u)) ed--;
    q[++ed] = u;
    while (now <= Q && s[now].y == u) {
      int l = st, r = ed, lalal;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (mid == ed || calc(q[mid], s[now].x, s[now].y) <
                             calc(q[mid + 1], s[now].x, s[now].y)) {
          lalal = mid;
          r = mid - 1;
        } else
          l = mid + 1;
      }
      ans[s[now].id] = calc(q[lalal], s[now].x, s[now].y);
      now++;
    }
  }
}
int read() {
  char ch = getchar();
  int x = 0;
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int main() {
  n = read();
  for (int u = 1; u <= n; u++) {
    a[u] = read();
    c[u] = c[u - 1] + a[u];
  }
  Q = read();
  for (int u = 1; u <= Q; u++) {
    s[u].x = read();
    s[u].y = read();
    s[u].id = u;
  }
  sort(s + 1, s + 1 + Q, cmp);
  solve();
  for (int u = 1; u <= Q; u++) printf("%d\n", ans[u]);
  return 0;
}
