#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0;
  char c = getchar();
  bool f = 0;
  for (; c > '9' || c < '0'; f = c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 1) + (x << 3) + c - '0', c = getchar())
    ;
  return f ? -x : x;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + 48);
}
const int N = 100000 + 10;
const double eps = 1e-8;
int n, m, a[N], s[N], top;
long long sum[N];
struct node {
  int x, y, id;
  long long ans;
} q[N];
bool cmp1(const node &a, const node &b) { return a.y < b.y; }
bool cmp2(const node &a, const node &b) { return a.id < b.id; }
double calc(int k, int j) {
  double yk = sum[k] - 1. * k * a[k], yj = sum[j] - 1. * j * a[j];
  return (yj - yk) / (a[k] - a[j]);
}
int main() {
  n = read();
  for (int i = 1, _y = n; i <= _y; ++i)
    a[i] = read(), sum[i] = sum[i - 1] + a[i];
  m = read();
  for (int i = 1, _y = m; i <= _y; ++i) q[i] = (node){read(), read(), i, 0};
  sort(q + 1, q + m + 1, cmp1);
  int j = 1;
  for (int i = 1, _y = n; i <= _y; ++i) {
    for (; top && a[s[top]] >= a[i]; --top)
      ;
    for (; top > 1 && calc(s[top - 1], i) - calc(s[top], i) > eps; --top)
      ;
    s[++top] = i;
    for (; j <= m && q[j].y == i; ++j) {
      int l = lower_bound(s + 1, s + top + 1, i - q[j].x + 1) - s, r = top - 1,
          now = i;
      for (; l <= r;) {
        int mid = (l + r) >> 1;
        if (calc(s[mid], s[mid + 1]) - (i - q[j].x) > eps)
          now = s[mid], r = mid - 1;
        else
          l = mid + 1;
      }
      q[j].ans = sum[i] - sum[now] + (long long)a[now] * (q[j].x - i + now);
    }
  }
  sort(q + 1, q + m + 1, cmp2);
  for (int i = 1, _y = m; i <= _y; ++i) write(q[i].ans), puts("");
}
