#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return {i, j};
}
template <class c>
auto dud(c *x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug &operator<<(const c &) {
    return *this;
  }
};
const int S = 20;
const int N = 1e5 + 7;
int n, q;
const int M = (1 << 17);
int tab[N];
int B[N];
int sum[N];
vector<int> D[2 * M];
int licz(int v, int c) {
  const vector<int> &T = D[v];
  int res = 2e9;
  if ((int)T.size() <= S) {
    for (int u : T) res = min(res, tab[u] * c + B[u]);
    return res;
  }
  int p = 0;
  int k = (int)T.size() - 1;
  while (p <= k) {
    if (p + 10 > k) {
      for (int i = p; i <= k; ++i) {
        res = min(res, tab[T[i]] * c + B[T[i]]);
      }
      return res;
    }
    int s = (p + k) / 2;
    int ws = tab[T[s]] * c + B[T[s]];
    int ws1 = tab[T[s + 1]] * c + B[T[s + 1]];
    res = min(res, ws);
    if (ws < ws1)
      k = s - 1;
    else
      p = s + 1;
  }
  return res;
}
int query(int i, int j) {
  int c = i - j;
  int a = max(1, j - i + 1);
  int b = j;
  a += M;
  b += M;
  int res = min(licz(a, c), licz(b, c));
  while (a / 2 != b / 2) {
    if (a % 2 == 0) res = min(res, licz(a + 1, c));
    if (b % 2 == 1) res = min(res, licz(b - 1, c));
    a /= 2;
    b /= 2;
  }
  return res + sum[j];
}
void zmniejszaj(vector<int> &w) {
  vector<int> res;
  sort(w.begin(), w.end(),
       [](int a, int b) -> bool { return tab[a] > tab[b]; });
  for (int u : w) {
    while ((int)res.size() > 1) {
      int u2 = res.back();
      res.pop_back();
      int u1 = res.back();
      if (1ll * (B[u] - B[u2]) * (tab[u1] - tab[u2]) >
          1ll * (B[u2] - B[u1]) * (tab[u2] - tab[u])) {
        res.push_back(u2);
        break;
      }
    }
    res.push_back(u);
  }
  w.swap(res);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", tab + i);
    sum[i] = sum[i - 1] + tab[i];
    B[i] = i * tab[i] - sum[i];
  }
  for (int i = 1; i <= n; ++i) D[M + i].push_back(i);
  for (int i = M - 1; i > 0; --i) {
    D[i].insert(D[i].end(), D[2 * i].begin(), D[2 * i].end());
    D[i].insert(D[i].end(), D[2 * i + 1].begin(), D[2 * i + 1].end());
    if ((int)D[i].size() > S) zmniejszaj(D[i]);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int i, j;
    scanf("%d %d", &i, &j);
    printf("%d\n", query(i, j));
  }
  return 0;
}
