#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

/* short */
using ull = unsigned long long;
using ll = long long;
using vec_i = vector<int>;
using vec_l = vector<ll>;
using vec_s = vector<string>;
using vec_b = vector<bool>;
using vec_d = vector<double>;
using dvec_i = vector<vec_i>;
using dvec_l = vector<vec_l>;
using dvec_s = vector<vec_s>;
using pair_i = pair<int, int>;
using pair_l = pair<ll, ll>;
using vec_pi = vector<pair_i>;
using vec_pl = vector<pair_l>;
using mint = modint998244353;
// using mint = modint1000000007;
// using mint = modint;

/* define */
#define _overload5(a, b, c, d, e, name, ...) name
#define _overload4(a, b, c, d, name, ...) name
#define _overload3(a, b, c, name, ...) name

#define _rep0(times) for(int rep_ins = 0; rep_ins < (int)(times); rep_ins++)
#define _rep1(i, times) for(int i = 0; i < (int)(times); i++)
#define _rep2(i, begin, end) for(int i = (int)(begin); i < (int)(end); i++)
#define _rep3(i, begin, end, space) for(int i = (int)(begin); i < (int)(end); i += (int)(space))
#define rep(...) _overload4(__VA_ARGS__, _rep3, _rep2, _rep1, _rep0)(__VA_ARGS__)

#define _rrep1(times) for(int rep_ins = (times) - 1;rep_ins >= 0;rep_ins--)
#define _rrep2(i,times) for(int i = (times) - 1;i >= 0;i--)
#define _rrep3(i,begin,end) for(int i = (begin) - 1;end >= (a);i--)
#define _rrep4(i,begin,end,space) for(int i = (begin) - 1;i >= (end);i -= space)
#define rrep(...) _overload4(__VA_ARGS__, _rrep4, _rrep3, _rrep2, _rrep1)(__VA_ARGS__)

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

#define _get1(i) cin >> (i)
#define _get2(i,j) cin >> (i) >> (j)
#define _get3(i,j,k) cin >> (i) >> (j) >> (k)
#define _get4(i,j,k,l) cin >> (i) >> (j) >> (k) >> (l)
#define get(...) _overload4(__VA_ARGS__, _get4, _get3, _get2, _get1)(__VA_ARGS__)
#define get_vec(a) for(auto& e: (a)){ cin >> e; }
#define get_dvec(a) for(auto& vec: (a)){ get_vec(vec); }

#define _out1(i) cout << (i) << endl
#define _out2(i,j) cout << (i) << " " << (j) << endl
#define _out3(i,j,k) cout << (i) << " " << (j) << " " << (k) << endl
#define _out4(i,j,k,l) cout << (i) << " " << (j) << " " << (k) << " " << (l) << endl
#define out(...) _overload4(__VA_ARGS__, _out4, _out3, _out2, _out1)(__VA_ARGS__)
#define _out_vec1(a) for(auto& e: (a)){ cout << e << " " ; } cout << endl
#define _out_vec2(a,i) auto start = a.begin()+i; auto end = a.end(); for(auto it = (start); it != (end); it++){ cout << *it << " " ; } cout << endl
#define _out_vec3(a,i,j) auto start = a.begin()+i; auto end = a.begin()+j; for(auto it = (start); it != (end); it++){ cout << *it << " " ; } cout << endl
#define _out_vec4(a,i,j,chr) auto start = a.begin()+i; auto end = a.begin()+j; for(auto it = (start); it != (end); it++){ cout << *it << (chr) ; } cout << endl
#define out_vec(...) _overload4(__VA_ARGS__, _out_vec4, _out_vec3, _out_vec2, _out_vec1)(__VA_ARGS__)
#define out_dvec_all(a) for(auto& vec: (a)){ out_vec_all(vec);}

#define outfirst cout << "First" << endl
#define outsecond cout << "Second" << endl
#define outyes cout << "Yes" << endl
#define outno cout << "No" << endl
#define outans cout << ans << endl

//const double PI =3.14159265359d;
//const double E =2.718281828d;

int main() {
    int R,n;
    get(R,n);
    vec_i a(n);
    for(auto& e:a) get(e);
    vec_i appears(1e6+100,0);
    for(auto e:a) appears[e] = 1;
    rep(i,appears.size()-1) appears[i+1] = appears[i]+appears[i+1];
    // rep(i,R) cout << appears[i] << " ";
    // cout << endl;
    int max_route = appears[appears.size()-1];
    int q;
    get(q);
    while(q--){
        int l,r;
        get(l,r);
        l--;
        int r_appers = r/R * max_route + appears[r%R];
        int l_appers = l/R * max_route + appears[l%R];
        int ans = r_appers - l_appers;
        outans;
    }
}