#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
const long long INF = 1000000000000000000LL;
int n;
int m;
int off = 1;
int lo;
int hi;
long long sum[N];
long long k;
struct line {
  long long k, l;
  line(long long _k = 0, long long _l = 0) {
    k = _k;
    l = _l;
  }
};
vector<line> T[(1 << 20) + 10];
inline int ccw(line A, line B, line C) {
  long long a = A.k * (B.l - C.l) + B.k * (C.l - A.l) + C.k * (A.l - B.l);
  if (a == 0) return 0;
  if (a < 0) return -1;
  return 1;
}
inline void load() {
  scanf("%d", &n);
  while (off < (n + 1)) off <<= 1;
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    sum[i] = sum[i - 1] + x;
    T[i + off].push_back(line(x, (long long)x * (i)-sum[i]));
  }
}
inline bool cmp(line A, line B) {
  if (A.k != B.k) return A.k < B.k;
  return A.l < B.l;
}
inline void merge(int x) {
  vector<line> hull;
  for (int i = 0; i < T[x * 2].size(); i++) hull.push_back(T[x * 2][i]);
  for (int i = 0; i < T[x * 2 + 1].size(); i++) hull.push_back(T[x * 2 + 1][i]);
  sort(hull.begin(), hull.end(), cmp);
  for (int i = 0; i < hull.size(); i++) {
    while (T[x].size() >= 2 &&
           ccw(T[x][T[x].size() - 2], T[x][T[x].size() - 1], hull[i]) <= 0)
      T[x].pop_back();
    T[x].push_back(hull[i]);
  }
}
inline long long eval(line A) { return A.k * k + A.l; }
inline long long query(int a, int b, int node) {
  if (a > hi || b < lo) return INF;
  if (a >= lo && b <= hi) {
    int low = 0, high = (int)T[node].size() - 2, middle;
    while (low <= high) {
      middle = (low + high) >> 1;
      if (eval(T[node][middle]) < eval(T[node][middle + 1]))
        high = middle - 1;
      else
        low = middle + 1;
    }
    long long sol = INF;
    for (int i = max(0, high - 5); i < min((int)T[node].size(), low + 5); i++) {
      sol = min(sol, eval(T[node][i]));
    }
    return sol;
  }
  return min(query(a, (a + b) / 2, node * 2),
             query((a + b) / 2 + 1, b, node * 2 + 1));
}
inline void solve() {
  for (int i = off - 1; i >= 1; i--) merge(i);
  scanf("%d", &m);
  while (m--) {
    int x, y;
    scanf("%d %d", &x, &y);
    lo = y - x + 1;
    hi = y;
    k = x - y;
    cout << query(0, off - 1, 1) + sum[y] << endl;
  }
}
int main(void) {
  load();
  solve();
  return 0;
}
