#include <bits/stdc++.h>
using namespace std;
int lungime , numar_muchii , capat[1000001];
inline int Distanta (const int nod_1 , const int nod_2)
{
return min(abs(nod_1 - nod_2) , 2 * lungime - abs(nod_1 - nod_2));
}
inline int Next (const int minim)
{
int stanga = 1 , dreapta = numar_muchii;
while (stanga <= dreapta)
{
const int mijloc = (stanga + dreapta) >> 1;
if (capat[mijloc] < minim) { stanga = mijloc + 1; }
else { dreapta = mijloc - 1; }
}
return stanga <= numar_muchii ? stanga : 1;
}
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int numar_intrebari;
cin >> lungime >> numar_muchii >> numar_intrebari;
for (int indice = 1 ; indice <= numar_muchii ; indice++)
{ cin >> capat[indice]; }
for (int indice = numar_muchii + 1 ; indice <= 2 * numar_muchii ; indice++)
{ capat[indice] = capat[indice - numar_muchii] + lungime; }
numar_muchii <<= 1;
while (numar_intrebari--)
{
int inceput , sfarsit;
cin >> inceput >> sfarsit;
int rezultat = Distanta(inceput , sfarsit) , locatie = Next(inceput);
rezultat = min(rezultat , Distanta(inceput , capat[locatie]) + 1 + Distanta((capat[locatie] + lungime) % (2 * lungime) , sfarsit));
if (locatie != 1) { locatie--; }
else { locatie = numar_muchii; }
rezultat = min(rezultat , Distanta(inceput , capat[locatie]) + 1 + Distanta((capat[locatie] + lungime) % (2 * lungime) , sfarsit));
cout << rezultat << '\n';
}
return 0;
}
