#include <bits/stdc++.h>
using namespace std;
struct Tnode {
  int val, down, st, len, size;
  Tnode *father, *son[2];
  Tnode() {}
  Tnode(Tnode *f, int v, int s) {
    val = v;
    down = 0;
    st = len = 2147483647;
    size = s;
    father = f;
    son[0] = son[1] = 0;
  }
} memory[1000050], *root;
int vs, data[1000050], answer[1000050], number[1000050];
pair<int, int> ask[1000050];
int Rand() { return (rand() << 15) | rand(); }
bool Cmp(int a, int b) { return ask[a].second < ask[b].second; }
void Down(Tnode *current) {
  if (!current) {
    return;
  }
  if (current->down != 0) {
    current->val += current->down;
    if (current->son[0]) {
      if (current->son[0]->st == 2147483647) {
        current->son[0]->down += current->down;
      } else {
        current->son[0]->st += current->down;
      }
    }
    if (current->son[1]) {
      if (current->son[1]->st == 2147483647) {
        current->son[1]->down += current->down;
      } else {
        current->son[1]->st += current->down;
      }
    }
    current->down = 0;
  }
  if (current->st != 2147483647) {
    current->val = current->st;
    if (current->son[0]) {
      current->val += current->son[0]->size * current->len;
    }
    if (current->son[0]) {
      current->son[0]->down = 0;
      current->son[0]->st = current->st;
      current->son[0]->len = current->len;
    }
    if (current->son[1]) {
      current->son[1]->down = 0;
      current->son[1]->st = current->val + current->len;
      current->son[1]->len = current->len;
    }
    current->st = current->len = 2147483647;
  }
  return;
}
void Update(Tnode *current) {
  if (!current) {
    return;
  }
  current->size = 1;
  if (current->son[0]) {
    current->size += current->son[0]->size;
  }
  if (current->son[1]) {
    current->size += current->son[1]->size;
  }
  return;
}
void Rotate(Tnode *current, int flag) {
  current->father->son[flag ^ 1] = current->son[flag];
  if (current->son[flag]) {
    current->son[flag]->father = current->father;
  }
  current->son[flag] = current->father;
  if (current->father->father) {
    current->father->father
        ->son[current->father->father->son[0] != current->father] = current;
  }
  current->father = current->father->father;
  current->son[flag]->father = current;
  Update(current->son[flag]);
  return;
}
void Splay(Tnode *current, Tnode *target) {
  while (current->father != target) {
    if (current->father->father == target) {
      Rotate(current, current->father->son[1] != current);
    } else if (current->father->father->son[0] == current->father &&
               current->father->son[0] == current) {
      Rotate(current->father, 1);
      Rotate(current, 1);
    } else if (current->father->father->son[1] == current->father &&
               current->father->son[1] == current) {
      Rotate(current->father, 0);
      Rotate(current, 0);
    } else {
      Rotate(current, current->father->son[1] != current);
      Rotate(current, current->father->son[1] != current);
    }
  }
  Update(current);
  if (!target) {
    root = current;
  }
  return;
}
int Findkth(Tnode *current, int len) {
  int total = 0;
  Tnode *best = current;
  while (current) {
    best = current;
    Down(current);
    total++;
    if (current->son[0]) {
      total += current->son[0]->size;
    }
    if (current->val < total * len) {
      total--;
      if (current->son[0]) {
        total -= current->son[0]->size;
      }
      current = current->son[0];
    } else {
      current = current->son[1];
    }
  }
  Splay(best, 0);
  return total;
}
void Find(int ask, Tnode *target) {
  Tnode *current = root;
  while (current) {
    Down(current);
    if (current->son[0]) {
      if (ask == current->son[0]->size + 1) {
        break;
      }
    } else if (ask == 1) {
      break;
    }
    if (current->son[0] && ask < current->son[0]->size + 1) {
      current = current->son[0];
    } else {
      ask--;
      if (current->son[0]) {
        ask -= current->son[0]->size;
      }
      current = current->son[1];
    }
  }
  Splay(current, target);
  return;
}
int all, check[1000050];
void Print(Tnode *current) {
  if (!current) {
    return;
  }
  Down(current);
  Print(current->son[0]);
  check[++all] = current->val;
  Print(current->son[1]);
  return;
}
int Read() {
  int result = 0;
  char flag = getchar();
  for (; flag < '0' || '9' < flag; flag = getchar())
    ;
  for (; '0' <= flag && flag <= '9'; flag = getchar()) {
    result = 10 * result + flag - 48;
  }
  return result;
}
int main() {
  int n, m, i, j, rank;
  srand((unsigned)time(0));
  n = Read();
  for (i = 1; i <= n; i++) {
    data[i] = Read();
  }
  m = Read();
  for (i = 1; i <= m; i++) {
    ask[i].first = Read();
    ask[i].second = Read();
    number[i] = i;
  }
  sort(number + 1, number + m + 1, Cmp);
  memory[++vs] = Tnode(0, 0, 2);
  root = &memory[vs];
  memory[++vs] = Tnode(root, 0, 1);
  root->son[1] = &memory[vs];
  for (i = j = 1; i <= n; i++) {
    Find(1, 0);
    Find(2, root);
    memory[++vs] = Tnode(root->son[1], 0, 1);
    root->son[1]->son[0] = &memory[vs];
    Update(root->son[1]);
    Update(root);
    Find(1, 0);
    Find(root->size, root);
    Down(root->son[1]->son[0]);
    root->son[1]->son[0]->down += data[i];
    rank = Findkth(root->son[1]->son[0], data[i]) + 1;
    Find(1, 0);
    Find(rank + 1, root);
    Down(root->son[1]->son[0]);
    root->son[1]->son[0]->st = data[i];
    root->son[1]->son[0]->len = data[i];
    for (; j <= m && ask[number[j]].second == i; j++) {
      Find(ask[number[j]].first + 1, 0);
      answer[number[j]] = root->val;
    }
  }
  for (i = 1; i <= m; i++) {
    printf("%d\n", answer[i]);
  }
  return 0;
}
