#include <bits/stdc++.h>
using namespace std;
int read() {
  int X = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
  return X * w;
}
const int N = 100000 + 10;
int n, Q, a[N], s[N];
long long ans[N];
vector<pair<int, int>> q[N];
int sta[N], top = 0;
long long X(int i) { return a[i]; }
long long Y(int i) { return 1ll * a[i] * i - s[i]; }
double slope(int i, int j) {
  if (X(i) == X(j))
    return Y(i) < Y(j) ? 1e18 : -1e18;
  else
    return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j));
}
long long F(int i, int k) { return Y(i) - k * X(i); }
int find(int lim) {
  int L = 1, R = top;
  while (L < R) {
    int mid = (L + R) >> 1;
    if (sta[mid] >= lim)
      R = mid;
    else
      L = mid + 1;
  }
  return L;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
  Q = read();
  for (int i = 1; i <= Q; ++i) {
    int x = read(), y = read();
    q[y].emplace_back(x, i);
  }
  for (int i = 1; i <= n; ++i) {
    while (top && a[sta[top]] >= a[i]) --top;
    while (top > 1 && slope(sta[top - 1], sta[top]) >= slope(sta[top], i))
      --top;
    sta[++top] = i;
    for (auto t : q[i]) {
      int x = t.first, id = t.second, k = i - x;
      int L = find(max(1, k)), R = top - 1;
      while (L < R) {
        int mid = (L + R + 1) >> 1;
        if (slope(sta[mid], sta[mid + 1]) <= k)
          L = mid;
        else
          R = mid - 1;
      }
      if (L < top && F(sta[L], k) > F(sta[L + 1], k)) ++L;
      ans[id] = F(sta[L], k) + s[i];
    }
  }
  for (int i = 1; i <= Q; ++i) printf("%lld\n", ans[i]);
  return 0;
}
