#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m;
int stk[N], top;
double a[N], s[N], ans[N];
vector<pair<int, int>> q[N];
inline double slope(int i, int j) {
  return (-s[i] + i * a[i] + s[j] - j * a[j]) / (a[i] - a[j]);
}
signed main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
  cin >> m;
  for (int i = 1, x, y; i <= m; ++i)
    cin >> x >> y, q[y].push_back(make_pair(x, i));
  for (int i = 1; i <= n; ++i) {
    while (top > 0 && a[stk[top]] >= a[i]) --top;
    while (top > 1 && slope(stk[top], i) <= slope(stk[top - 1], i)) --top;
    stk[++top] = i;
    for (auto p : q[i]) {
      int lt = upper_bound(stk + 1, stk + top + 1, i - p.first) - stk,
          rt = top - 1, mid, ret = i;
      while (lt <= rt) {
        if (mid = lt + rt >> 1, slope(stk[mid], stk[mid + 1]) >= i - p.first)
          rt = mid - 1, ret = stk[mid];
        else
          lt = mid + 1;
      }
      ans[p.second] = s[i] - s[ret] + a[ret] * (ret + p.first - i);
    }
  }
  for (int i = 1; i <= m; ++i)
    cout << fixed << setprecision(0) << ans[i] << endl;
}
