#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
pair<int, int> poi[N];
bool cmp(pair<int, int> x, pair<int, int> y) { return x.first == y.first; }
bool Judge(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  return (long long)(a.first - c.first) * (b.second - c.second) >
         (long long)(b.first - c.first) * (a.second - c.second);
}
void init_(vector<pair<int, int> >& vec, int l, int r) {
  vector<pair<int, int> > que;
  for (int i = l; i <= r - 1; i++) que.push_back(poi[i]);
  sort(que.begin(), que.end());
  reverse(que.begin(), que.end());
  que.resize(unique(que.begin(), que.end(), cmp) - que.begin());
  reverse(que.begin(), que.end());
  for (int i = 0; i <= (int)que.size() - 1; i++) {
    pair<int, int> a = que[i];
    while (vec.size() > 1) {
      pair<int, int> b = vec[vec.size() - 1];
      pair<int, int> c = vec[vec.size() - 2];
      if (Judge(a, b, c)) break;
      vec.pop_back();
    }
    vec.push_back(a);
  }
}
long long calc(pair<int, int> a, long long x) { return a.first * x + a.second; }
int query(vector<pair<int, int> >& vec, int x) {
  int l = 0;
  int r = vec.size();
  while (l != r - 1) {
    if (calc(vec[((l + r) >> 1) - 1], x) < calc(vec[((l + r) >> 1)], x))
      l = ((l + r) >> 1);
    else
      r = ((l + r) >> 1);
  }
  return calc(vec[l], x);
}
vector<pair<int, int> > vec[N << 2];
void Build(int k, int l, int r) {
  init_(vec[k], l, r);
  if (l == r - 1) return;
  Build((k << 1), l, ((l + r) >> 1));
  Build(((k << 1) + 1), ((l + r) >> 1), r);
}
int query(int k, int l, int r, int t, int v, int s) {
  if (v <= l || r <= t) return 0;
  if (t <= l && r <= v) return query(vec[k], s);
  int x = query((k << 1), l, ((l + r) >> 1), t, v, s);
  int y = query(((k << 1) + 1), ((l + r) >> 1), r, t, v, s);
  return max(x, y);
}
int val[N], sum[N];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d\n", val + i);
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + val[i];
  for (int i = 1; i <= n; i++)
    poi[i] = pair<int, int>(val[i], sum[i] - i * val[i]);
  Build(1, 1, n + 1);
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &y, &x);
    y = x - y;
    int ans = query(1, 1, n + 1, y, x + 1, y);
    printf("%d\n", sum[x] - ans);
  }
  return 0;
}
