#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<double>
using namespace std;
const int mxn=1e6+5;
vector<int>v,vv;
vector<t3>qr;
struct seg{
int t[2*mxn]{0};
void build(){
for(int i=0;i<2*mxn;i++)t[i]=2e9;
}
void upd(int i,int sz,int amt){
i+=sz;t[i]=min(t[i],amt);
for(i>>=1;i;i>>=1)t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int l,int r,int sz,int rs=2e9){
for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
if(l&1)rs=min(rs,t[l++]);
if(r&1)rs=min(rs,t[--r]);
}return rs;
}
}sg[8];
int ans[mxn]{0};
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m,q;cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int x;cin>>x;v.pb(x);vv.pb(x+n);
}int x=v.size();
for(int i=0;i<q;i++){
int l,r;cin>>l>>r;
qr.pb({l,r,i});qr.pb({r,l,i});
ans[i] = min(2*n-abs(l-r),abs(l-r));
}sort(all(qr));int idx=0;
for(int i=0;i<8;i++)sg[i].build();
for(auto [l,r,i] : qr){
while(idx<v.size()&&v[idx]<=l){
sg[0].upd(idx,x,-v[idx]-v[idx]-n);
sg[1].upd(idx,x,2*n+v[idx]-v[idx]-n);
sg[2].upd(idx,x,2*n+v[idx]+2*n+v[idx]+n);
sg[3].upd(idx,x,-v[idx]+2*n+v[idx]+n);
sg[4].upd(idx,x,-v[idx]+v[idx]+n);
sg[5].upd(idx,x,-v[idx]+2*n-v[idx]-n);
sg[6].upd(idx,x,2*n+v[idx]+2*n-v[idx]-n);
sg[7].upd(idx,x,2*n+v[idx]+v[idx]+n);
idx++;
}int tl=ub(vv,r),tr=lb(vv,r);
ans[i]=min(ans[i],1+l+r+min(sg[0].qr(0,tl,x),sg[5].qr(tr,x,x)));
ans[i]=min(ans[i],1+l-r+min(sg[3].qr(0,tl,x),sg[4].qr(tr,x,x)));
ans[i]=min(ans[i],1-l+r+min(sg[1].qr(0,tl,x),sg[6].qr(tr,x,x)));
ans[i]=min(ans[i],1-l-r+min(sg[2].qr(0,tl,x),sg[7].qr(tr,x,x)));
}for(int i=0;i<8;i++)sg[i].build();
reverse(all(qr));idx=v.size()-1;
for(auto [l,r,i] : qr){
while(idx>=0&&v[idx]>=l){
sg[0].upd(idx,x,v[idx]-v[idx]-n);
sg[1].upd(idx,x,2*n-v[idx]-v[idx]-n);
sg[2].upd(idx,x,2*n-v[idx]+2*n+v[idx]+n);
sg[3].upd(idx,x,v[idx]+2*n+v[idx]+n);
sg[4].upd(idx,x,v[idx]+v[idx]+n);
sg[5].upd(idx,x,v[idx]+2*n-v[idx]-n);
sg[6].upd(idx,x,2*n-v[idx]+2*n-v[idx]-n);
sg[7].upd(idx,x,2*n-v[idx]+v[idx]+n);
idx--;
}int tl=ub(vv,r),tr=lb(vv,r);
ans[i]=min(ans[i],1-l+r+min(sg[0].qr(0,tl,x),sg[5].qr(tr,x,x)));
ans[i]=min(ans[i],1-l-r+min(sg[3].qr(0,tl,x),sg[4].qr(tr,x,x)));
ans[i]=min(ans[i],1+l+r+min(sg[1].qr(0,tl,v.size()),sg[6].qr(tr,x,x)));
ans[i]=min(ans[i],1+l-r+min(sg[2].qr(0,tl,v.size()),sg[7].qr(tr,x,x)));
}
for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
