#include<bits/stdc++.h> using namespace std; const int NMAX = 5*1e5; #define int long long vector<int> pairs(NMAX); int nbTotal; int coutchemin(int a, int b) { if(b < a) swap(a, b); return min(b-a, nbTotal-b + a); } signed main() { ios::sync_with_stdio(false); cin.tie(0); int nbMoitie, nbPairs, nbRequetes; cin >> nbMoitie >> nbPairs >> nbRequetes; // cout << nbPairs << endl; pairs.resize(nbPairs); nbTotal = nbMoitie*2; for(int i = 0; i < nbPairs; i++) { cin >> pairs[i]; } sort(pairs.begin(), pairs.end());//TODO for(int iRequete = 0; iRequete < nbRequetes; iRequete++) { // cout << "jlkj" << endl; int dep, fin; cin >> dep >> fin; if(dep > fin) swap(dep, fin); int meillDist = nbTotal; meillDist = coutchemin(dep, fin); int depBis = 0; int iDepBis; if(dep >= nbMoitie) { iDepBis = lower_bound(pairs.begin(), pairs.end(), dep-nbMoitie)-pairs.begin(); } else iDepBis = lower_bound(pairs.begin(), pairs.end(), dep)-pairs.begin(); int iDepBisAv = iDepBis-1; if(iDepBis >= nbPairs) { iDepBis = 0; } //cout << "idepbisav : " << iDepBisAv << endl; if(iDepBisAv < 0) iDepBisAv = nbPairs-1; // cout << "idepbisav : " << iDepBisAv << endl; //iBis // cout << "d" << endl; // cout << meillDist << endl; meillDist = min(meillDist, coutchemin(dep, pairs[iDepBis]+nbMoitie)+1+coutchemin(fin, pairs[iDepBis])); meillDist = min(meillDist, coutchemin(dep, pairs[iDepBis])+1+coutchemin(fin, pairs[iDepBis]+nbMoitie)); // cout << meillDist << endl; // cout << "idepbisav : " << iDepBisAv << endl; meillDist = min(meillDist, coutchemin(dep, pairs[iDepBisAv]+nbMoitie)+1+coutchemin(fin, pairs[iDepBisAv])); meillDist = min(meillDist, coutchemin(dep, pairs[iDepBisAv])+1+coutchemin(fin, pairs[iDepBisAv]+nbMoitie)); cout << meillDist << "\n"; } }