#include <bits/stdc++.h>
using namespace std;
template <typename T>
void scan(T &angka) {
  angka = 0;
  char input = getchar();
  T kali = 1;
  while (!(48 <= input && input <= 57)) {
    if (input == '-') kali = -1;
    input = getchar();
  }
  while (48 <= input && input <= 57)
    angka = (angka << 3) + (angka << 1) + input - 48, input = getchar();
  angka *= kali;
}
template <typename T1, typename T2>
void scan(T1 &angka1, T2 &angka2) {
  scan(angka1);
  scan(angka2);
}
const int MAXK = 100000;
const int MAXQ = 100000;
const int treesize = 131072;
struct trio {
  int first, second, th;
  trio(int _fi, int _se, int _th) {
    first = _fi;
    second = _se;
    th = _th;
  }
  trio() {}
  bool operator<(const trio &other) const {
    if (first != other.first) return (first < other.first);
    if (second != other.second) return (second < other.second);
    return (th < other.th);
  }
};
struct segtree {
  int terbesar, pilihan;
  segtree(int _terbesar, int _pilihan) {
    terbesar = _terbesar, pilihan = _pilihan;
  }
  segtree() {}
  bool operator<(const segtree &other) const {
    if (terbesar != other.terbesar) return (terbesar < other.terbesar);
    return (pilihan > other.pilihan);
  }
};
int totalgram, totalbalik, posbalik[MAXK + 5], batas = -1, nilai[MAXK + 5];
bool batasfix = false;
set<pair<int, int> > poshenti;
vector<int> event;
vector<trio> querylist;
int ans[MAXQ + 5], q, idxquery = 0;
int lazy[(treesize << 1) + 5] = {};
segtree tree[(treesize << 1) + 5], dummy(-1, -1);
void pullup(int indeks) {
  tree[indeks] = max(tree[indeks << 1], tree[(indeks << 1) | 1]);
}
void pushdown(int indeks) {
  tree[(indeks << 1)].terbesar += lazy[indeks];
  lazy[(indeks << 1)] += lazy[indeks];
  tree[(indeks << 1) | 1].terbesar += lazy[indeks];
  lazy[(indeks << 1) | 1] += lazy[indeks];
  lazy[indeks] = 0;
}
void buatsegtree(int kiri, int kanan, int indeks) {
  lazy[indeks] = 0;
  if (kiri == kanan) {
    tree[indeks].terbesar = nilai[kiri];
    tree[indeks].pilihan = kiri;
    assert(tree[indeks].terbesar <= totalgram);
    return;
  }
  int mid = (kiri + kanan) >> 1;
  buatsegtree(kiri, mid, indeks << 1);
  buatsegtree(mid + 1, kanan, (indeks << 1) | 1);
  pullup(indeks);
  assert(tree[indeks].terbesar <= totalgram);
}
void buatsegtree() { buatsegtree(0, totalbalik, 1); }
void update(int kiri, int kanan, int indeks, int l, int r, int tambah) {
  if (l <= kiri && kanan <= r) {
    lazy[indeks] += tambah;
    tree[indeks].terbesar += tambah;
    assert(tree[indeks].terbesar <= totalgram);
    return;
  }
  if (l > kanan || r < kiri) return;
  pushdown(indeks);
  int mid = (kiri + kanan) >> 1;
  update(kiri, mid, indeks << 1, l, r, tambah);
  update(mid + 1, kanan, (indeks << 1) | 1, l, r, tambah);
  pullup(indeks);
}
void update(int l, int r, int tambah) {
  update(0, totalbalik, 1, l, r, tambah);
}
segtree query(int kiri, int kanan, int indeks, int l, int r) {
  if (l <= kiri && kanan <= r) return tree[indeks];
  if (l > kanan || r < kiri) return dummy;
  pushdown(indeks);
  int mid = (kiri + kanan) >> 1;
  return max(query(kiri, mid, indeks << 1, l, r),
             query(mid + 1, kanan, (indeks << 1) | 1, l, r));
}
segtree query(int l, int r) { return query(0, totalbalik, 1, l, r); }
int gradien(int indeks) {
  if (indeks & 1)
    return -1;
  else
    return 1;
}
void masukkanevent(long long waktu) {
  if (waktu > totalgram) return;
  event.push_back(waktu);
}
void buatevent() {
  for (int i = 0; i < q; i++) masukkanevent(querylist[i].first);
  auto it = poshenti.begin();
  int mulaiupdate = 0;
  for (int i = 1; i <= totalbalik; i++) {
    while ((it != poshenti.end()) && (it->first <= posbalik[i])) {
      mulaiupdate += posbalik[i] - it->first;
      it = next(it);
      masukkanevent(mulaiupdate);
    }
    masukkanevent(mulaiupdate + (totalgram - nilai[i]));
  }
  masukkanevent(totalgram);
}
bool isfix() {
  if (batas == -1) return false;
  if (poshenti.size() == 0) return true;
  if (posbalik[batas] <= poshenti.begin()->first) return true;
}
int tentbatas() {
  if (batasfix) return batas;
  if (poshenti.size()) return poshenti.begin()->second;
  return totalbalik;
}
void updatebatas(int batasupdate) {
  auto temp = query(0, batasupdate);
  if (temp.terbesar == totalgram) batas = temp.pilihan - 1;
}
int binser(int waktu) {
  int bawah = 1, atas = totalbalik, mid;
  while (bawah <= atas) {
    mid = (bawah + atas) >> 1;
    if (posbalik[mid] >= waktu)
      atas = mid - 1;
    else
      bawah = mid + 1;
  }
  if (bawah > totalbalik || posbalik[bawah] > waktu) return atas;
  return bawah;
}
void jawabquery(int gramawal) {
  while (idxquery < querylist.size()) {
    auto kwery = querylist[idxquery];
    if (kwery.first != gramawal) break;
    int posnow = kwery.second;
    int tempatbalik = binser(kwery.second);
    ans[kwery.th] = (query(tempatbalik, tempatbalik).terbesar) +
                    (gradien(tempatbalik)) * (posnow - posbalik[tempatbalik]);
    ans[kwery.th] = min(totalgram, ans[kwery.th]);
    ans[kwery.th] = max(0, ans[kwery.th]);
    idxquery++;
  }
}
void updateposhenti(int delta) {
  auto temp = *poshenti.begin();
  poshenti.erase(temp);
  assert(temp.first + delta <= posbalik[temp.second + 1]);
  if (temp.first + delta != posbalik[temp.second + 1]) {
    temp.first += delta;
    poshenti.insert(temp);
  }
}
void printsemua() {
  cout << endl;
  cout << "printing all" << endl;
  for (int i = 1; i <= totalbalik; i++) cout << query(i, i).terbesar << " ";
  cout << endl << endl << endl;
}
void linesweep() {
  sort((event).begin(), (event).end());
  event.resize(unique((event).begin(), (event).end()) - event.begin());
  batasfix = (isfix());
  int tadi = 0, delta;
  for (int noevent = 0; noevent < event.size(); noevent++) {
    delta = event[noevent] - tadi;
    tadi = event[noevent];
    int batasupdate = tentbatas();
    update(0, batasupdate, delta);
    updatebatas(batasupdate);
    if (!batasfix && poshenti.size()) updateposhenti(delta);
    if (!batasfix) batasfix = isfix();
    jawabquery(event[noevent]);
  }
}
void simulasikan() {
  int now = 0, tadi;
  nilai[0] = now;
  for (int i = 1; i <= totalbalik; i++) {
    tadi = now;
    now += gradien(i - 1) * (posbalik[i] - posbalik[i - 1]);
    if (now < 0) {
      poshenti.insert(make_pair(posbalik[i - 1] + tadi, i - 1));
      now = 0;
    } else if (now >= totalgram) {
      if (batas == -1) batas = i - 1;
      now = totalgram;
    }
    nilai[i] = now;
  }
}
void perbaikians() {
  for (int i = 0; i < q; i++) ans[i] = totalgram - ans[i];
}
void jawabsemua() {
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}
void printurutanquery() {
  cout << "ini urutannya " << endl;
  for (auto kweri : querylist) cout << kweri.th << " ";
  cout << endl;
}
int main() {
  scan(totalgram, totalbalik);
  posbalik[0] = 0;
  for (int i = 1; i <= totalbalik; i++) scan(posbalik[i]);
  scan(q);
  querylist.resize(q);
  for (int i = 0; i < q; i++) {
    querylist[i].th = i;
    scan(querylist[i].second, querylist[i].first);
    querylist[i].first = totalgram - querylist[i].first;
  }
  sort((querylist).begin(), (querylist).end());
  simulasikan();
  buatsegtree();
  buatevent();
  linesweep();
  perbaikians();
  jawabsemua();
  assert(batas == -1);
}
