#include <bits/stdc++.h>
using namespace std;
const int N = 101000;
vector<pair<int, int> > nd[N * 4];
pair<int, int> pnt[N];
int s[N], a[N], m, x, y, n;
bool cmp(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  return 1ll * (b.second - a.second) * (c.first - a.first) >=
         1ll * (c.second - a.second) * (b.first - a.first);
}
void build(int l, int r, vector<pair<int, int> > &x) {
  vector<pair<int, int> > c;
  for (int i = l; i < (int)r + 1; i++) c.push_back(pnt[i]);
  sort(c.begin(), c.end());
  for (int i = 0; i < (int)((int)(c).size()); i++) {
    if (((int)(x).size()) && c[i].first == x.back().first) continue;
    while (((int)(x).size()) >= 2 &&
           cmp(x[((int)(x).size()) - 2], x[((int)(x).size()) - 1], c[i]))
      x.pop_back();
    x.push_back(c[i]);
  }
}
void build(int p, int l, int r) {
  build(l, r, nd[p]);
  if (l != r) {
    int md = (l + r) >> 1;
    build(p + p, l, md);
    build(p + p + 1, md + 1, r);
  }
}
int ask(vector<pair<int, int> > &x, int k) {
  int l = 0, r = ((int)(x).size()) - 1;
  while (l + 4 < r) {
    int pl = (l + l + r) / 3, pr = (l + r + r) / 3;
    if (x[pl].first * k + x[pl].second >= x[pr].first * k + x[pr].second)
      l = pl;
    else
      r = pr;
  }
  int ans = x[r].first * k + x[r].second;
  for (int i = l; i < (int)r; i++) ans = min(ans, x[i].first * k + x[i].second);
  return ans;
}
int ask(int p, int l, int r, int tl, int tr, int k) {
  if (l == tl && r == tr)
    return ask(nd[p], k);
  else {
    int md = (l + r) >> 1;
    if (tr <= md)
      return ask(p + p, l, md, tl, tr, k);
    else if (tl > md)
      return ask(p + p + 1, md + 1, r, tl, tr, k);
    else
      return min(ask(p + p, l, md, tl, md, k),
                 ask(p + p + 1, md + 1, r, md + 1, tr, k));
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < (int)n + 1; i++)
    scanf("%d", a + i), s[i] = s[i - 1] + a[i];
  for (int i = 1; i < (int)n + 1; i++)
    pnt[i] = make_pair(a[i], a[i] * i - s[i]);
  build(1, 1, n);
  for (scanf("%d", &m); m; m--) {
    scanf("%d%d", &x, &y);
    printf("%d\n", ask(1, 1, n, y - x + 1, y, x - y) + s[y]);
  }
}
