#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
const long long SIZE = 1e6 + 5;
long long n, q;
long long sta[SIZE], a[SIZE], sum[SIZE], f[SIZE];
struct node {
  long long x, y, idx;
  bool operator<(const node &a) const { return y < a.y; }
} que[SIZE];
namespace GTR {
const long long bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline long long fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline long long read() {
  long long a = 0, b = 1, c = fetch();
  while (c < 48 || c > 57) b ^= c == '-', c = fetch();
  while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace GTR
using GTR::read;
double slope(long long i, long long j) {
  return double((sum[i] - (a[i] * i)) - (sum[j] - a[j] * j)) /
         double(a[i] - a[j]);
}
long long find(long long x, long long top) {
  long long l = 1, r = top, mid = 0;
  while (l < r) {
    mid = (l + r) >> 1;
    if (sta[mid] < x)
      l = mid + 1;
    else
      r = mid;
  }
  return l;
}
signed main() {
  n = read();
  for (long long i = 1; i <= n; ++i) a[i] = read(), sum[i] = sum[i - 1] + a[i];
  q = read();
  for (long long i = 1; i <= q; ++i)
    que[i].x = read(), que[i].y = read(), que[i].idx = i;
  std::sort(que + 1, que + q + 1);
  long long top = 0;
  for (long long i = 1, j = 1; i <= n; ++i) {
    while (top && a[sta[top]] >= a[i]) --top;
    while (top > 1 && slope(sta[top], i) >= slope(sta[top - 1], i)) --top;
    sta[++top] = i;
    for (; que[j].y == i && j <= q;) {
      long long l = find(que[j].y - que[j].x, top), r = top, mid = 0;
      while (l < r) {
        mid = (l + r) >> 1;
        if (slope(sta[mid], sta[mid + 1]) < que[j].x - que[j].y)
          r = mid;
        else
          l = mid + 1;
      }
      l = sta[l], r = que[j].y,
      f[que[j].idx] = sum[r] - sum[l] + (que[j].x - (r - l)) * a[l], ++j;
    }
  }
  for (long long i = 1; i <= q; ++i) printf("%lld\n", f[i]);
  return 0;
}
