#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1, c = getchar();
  while (c < 48) c == '-' && (f = -1), c = getchar();
  while (c > 47) x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int MAXN = 100005;
int rep[MAXN], enp[MAXN], arr[MAXN];
int idx[MAXN], rt[MAXN];
int n, q;
long long pre[MAXN];
namespace Bit {
int c[MAXN];
inline void modify(int x, int k) {
  while (x <= n) c[x] += k, x += x & -x;
}
inline int query(int x) {
  int res = 0;
  while (x) res += c[x], x -= x & -x;
  return res;
}
inline int calc_idx(int x) {
  int l = 1, r = n, res = n + 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (query(mid) > x)
      res = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return modify(res, -1), res;
}
}  // namespace Bit
namespace Seg {
int tot;
int ls[MAXN * 200], rs[MAXN * 200], sum[MAXN * 200];
void modify(int &x, int y, int l, int r, int k) {
  ls[x = ++tot] = ls[y];
  rs[x] = rs[y];
  sum[x] = sum[y] + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (k <= mid) modify(ls[x], ls[y], l, mid, k);
  if (k > mid) modify(rs[x], rs[y], mid + 1, r, k);
}
int qrnk(int x, int l, int r, int k) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (sum[ls[x]] > k) return qrnk(ls[x], l, mid, k);
  return qrnk(rs[x], mid + 1, r, k - sum[ls[x]]);
}
int qsum(int x, int l, int r, int k) {
  if (r <= k) return sum[x];
  int mid = (l + r) >> 1, res = 0;
  if (k > mid) res += qsum(rs[x], mid + 1, r, k);
  return res + qsum(ls[x], l, mid, k);
}
}  // namespace Seg
pair<long long, int> calc(int t, int in, int k) {
  in += rep[t] - k;
  int res = upper_bound(rep, rep + n, in) - rep;
  return make_pair((long long)in * res - pre[res], res);
}
inline int query_out(int x, int k) {
  int l = 0, r = n - 1, res = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (calc(mid, 0, k).first <= x)
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}
inline int query_in(int t, int x, int k) {
  int l = 0, r = rep[t + 1] - rep[t], res = -1;
  if (t == n - 1) r = x / n + k + 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (calc(t, mid, k).first <= x)
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}
int main(int argc, char const *argv[]) {
  n = read();
  q = read();
  for (int i = 0; i < n; ++i) arr[i] = read();
  int stp = arr[0];
  for (int i = 0; i < n; ++i) arr[i] -= stp;
  for (int i = 1; i < n; ++i) {
    rep[i] = rep[i - 1] + (arr[i] - enp[i - 1]) / i;
    enp[i] = enp[i - 1] + (rep[i] - rep[i - 1]) * i;
    pre[i + 1] = pre[i] + rep[i];
  }
  for (int i = 1; i <= n; ++i) Bit::modify(i, 1);
  for (int i = n - 1; ~i; --i) idx[i] = Bit::calc_idx(arr[i] - enp[i]) - 1;
  for (int i = 0; i < n; ++i) Seg::modify(rt[i + 1], rt[i], 0, n - 1, idx[i]);
  for (int i = 1, x, k; i <= q; ++i) {
    x = read();
    k = read();
    if (x < stp) {
      printf("%d\n", x);
      continue;
    }
    x -= stp;
    int a = query_out(x, k), b = query_in(a, x, k);
    auto res = calc(a, b, k);
    int rem = x - res.first, rk = Seg::qrnk(rt[res.second], 0, n - 1, rem);
    printf("%lld\n", stp + enp[a] + (long long)b * (a + 1) +
                         (rk ? Seg::qsum(rt[a + 1], 0, n - 1, rk - 1) : 0));
  }
  return 0;
}
