#include <bits/stdc++.h>
using namespace std;
long long ans[100005], sum[100005];
int x[100005];
vector<pair<int, int> > q[100005];
int st[100005];
inline double gk(int i, int j) {
  double yi = sum[i] - (double)i * x[i], yj = sum[j] - (double)j * x[j];
  return (yi - yj) / (x[i] - x[j]);
}
int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", x + i);
    sum[i] = sum[i - 1] + x[i];
  }
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    q[r].push_back(make_pair(l, i));
  }
  int tp = 0;
  for (int i = 1; i <= n; ++i) {
    while (tp && x[st[tp]] >= x[i]) --tp;
    while (1 < tp && gk(st[tp], i) >= gk(st[tp - 1], i)) --tp;
    st[++tp] = i;
    for (vector<pair<int, int> >::iterator it = q[i].begin(); it != q[i].end();
         ++it) {
      int l = lower_bound(st + 1, st + tp + 1, i - it->first + 1) - st;
      int r = tp - 1, mid, rp = i;
      while (l <= r) {
        mid = l + r >> 1;
        if (gk(st[mid], st[mid + 1]) <= it->first - i)
          rp = st[mid], r = mid - 1;
        else
          l = mid + 1;
      }
      ans[it->second] = sum[i] - sum[rp] + x[rp] * (it->first + rp - i);
    }
  }
  for (int i = 0; i < m; ++i) printf("%I64d\n", ans[i]);
  return 0;
}
