#include <bits/stdc++.h>
using namespace std;
const int N = 114514;
double s[N], a[N];
int n, q, r, kkr[N], st[N];
vector<pair<int, int>> v[N];
double slo(int x, int y) {
  return (s[y] - y * a[y] + x * a[x] - s[x]) / (a[x] - a[y]);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lf", &a[i]), s[i] = s[i - 1] + a[i];
  scanf("%d", &q);
  slo(1, 4);
  for (int i = 1, x, y; i <= q; i++)
    scanf("%d%d", &x, &y), v[y].push_back({x, i});
  for (int i = 1; i <= n; i++) {
    while (r && a[st[r]] >= a[i]) r--;
    while (r > 1 && slo(st[r], i) <= slo(st[r - 1], i)) r--;
    st[++r] = i;
    for (auto p : v[i]) {
      int xs = upper_bound(st + 1, st + r + 1, i - p.first) - st, xt = r - 1,
          mi, as = i;
      while (xs <= xt) {
        mi = ((xs + xt) >> 1);
        if (slo(st[mi], st[mi + 1]) >= i - p.first)
          xt = mi - 1, as = st[mi];
        else
          xs = mi + 1;
      }
      kkr[p.second] = s[i] - s[as] + a[as] * (as + p.first - i);
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", kkr[i]);
}
