#include <bits/stdc++.h>
using namespace std;
class ConvexHullTrick {
 public:
  vector<long long int> a, b;
  int size = -1;
  bool can_remove(int a, int b, int c, int d) {
    if (a / b != c / d) return a / b < c / d;
    a %= b;
    c %= d;
    if (a == 0) return true;
    if (c == 0) return false;
    return can_remove(d, c, b, a);
  }
  void add(long long int i, long long int j) {
    size++;
    a.push_back(i);
    b.push_back(j);
    while (size >= 2 &&
           can_remove(b[size - 1] - b[size], a[size] - a[size - 1],
                      b[size - 2] - b[size - 1], a[size - 1] - a[size - 2])) {
      a.erase(a.end() - 2);
      b.erase(b.end() - 2);
      size--;
    }
  }
  double iniInterval(int i) {
    if (i == 0) return -1000000010;
    return ((double)b[i] - b[i - 1]) / (a[i - 1] - a[i]);
  }
  long long int query(int x) {
    int i = 0, j = size;
    while (i < j) {
      int m = (i == j - 1) ? j : (i + j) / 2;
      if (iniInterval(m) <= (double)x)
        i = m;
      else
        j = m - 1;
    }
    return a[i] * x + b[i];
  }
};
struct node {
  int ini, fim;
  ConvexHullTrick CHT;
} SEG[4 * 100010];
int n, q, n1, n2;
int v[100010];
long long int sv[100010];
void merge(int i, int f1, int f2) {
  int p = 0, q = 0;
  for (; p <= SEG[f1].CHT.size && q <= SEG[f2].CHT.size;) {
    long long int a1 = SEG[f1].CHT.a[p];
    long long int b1 = SEG[f1].CHT.b[p];
    long long int a2 = SEG[f2].CHT.a[q];
    long long int b2 = SEG[f2].CHT.b[q];
    if (a1 == a2) {
      SEG[i].CHT.add(a1, min(b1, b2));
      p++;
      q++;
    } else if (a1 > a2) {
      SEG[i].CHT.add(a1, b1);
      p++;
    } else {
      SEG[i].CHT.add(a2, b2);
      q++;
    }
  }
  for (; p <= SEG[f1].CHT.size;) {
    SEG[i].CHT.add(SEG[f1].CHT.a[p], SEG[f1].CHT.b[p]);
    p++;
  }
  for (; q <= SEG[f2].CHT.size;) {
    SEG[i].CHT.add(SEG[f2].CHT.a[q], SEG[f2].CHT.b[q]);
    q++;
  }
}
void build(int id, int i, int j) {
  SEG[id].ini = i;
  SEG[id].fim = j;
  if (i == j) return void(SEG[id].CHT.add(v[i], v[i] * i - sv[i]));
  int m = (i + j) / 2;
  build(2 * id, i, m);
  build(2 * id + 1, m + 1, j);
  merge(id, 2 * id, 2 * id + 1);
}
long long int query(int id, int i, int j, int k) {
  if (SEG[id].ini > j || SEG[id].fim < i)
    return ((long long int)1000000010) * 1000000010;
  if (SEG[id].ini >= i && SEG[id].fim <= j) return SEG[id].CHT.query(k);
  return min(query(2 * id, i, j, k), query(2 * id + 1, i, j, k));
}
int main() {
  scanf("%d", &n);
  for (int g = 1; g <= n; g++) {
    scanf("%d", &v[g]);
    sv[g] = sv[g - 1] + v[g];
  }
  build(1, 1, n);
  scanf("%d", &q);
  for (int g = 0; g < q; g++) {
    scanf("%d %d", &n1, &n2);
    printf("%lld\n", query(1, n2 - n1 + 1, n2, n1 - n2) + sv[n2]);
  }
}
