#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, s[(100009)], top, a[(100009)];
long long sum[(100009)], ans[(100009)];
vector<pair<int, int> > ask[(100009)];
vector<pair<int, int> >::iterator it;
double slope(int k, int j) {
  double yk = sum[k] - (double)k * a[k], yj = sum[j] - (double)j * a[j];
  return (yk - yj) / (a[k] - a[j]);
}
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 = 0; i <= n; ++i) ask[i].clear();
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &x, &y);
    ask[y].push_back(make_pair(x, i));
  }
  for (int i = 1; i <= n; ++i) {
    while (top > 0 && a[s[top]] >= a[i]) --top;
    while (top > 1 && slope(s[top], i) >= slope(s[top - 1], i)) --top;
    s[++top] = i;
    for (it = ask[i].begin(); it != ask[i].end(); ++it) {
      int x = it->first, y = it->second;
      int l = lower_bound(s + 1, s + top + 1, i - x + 1) - s, r = top - 1,
          pos = i;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (slope(s[mid], s[mid + 1]) <= x - i)
          pos = s[mid], r = mid - 1;
        else
          l = mid + 1;
      }
      ans[y] = sum[i] - sum[pos] + (long long)a[pos] * (x + pos - i);
    }
  }
  for (int i = 0; i < m; ++i) printf("%lld\n", ans[i]);
}
