#include using namespace std; int main() { int R, N; cin >> R >> N; vector A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } vector appear(R); for (int i = 0; i < N; i++) { appear[A[i]] = 1; } vector sum(R + 1); for (int i = 1; i <= R; i++) { sum[i] = sum[i - 1] + appear[i - 1]; } int Q; cin >> Q; while (Q--) { int l, r; cin >> l >> r; long long len = r - l + 1; long long ans = 0; ans += len / R * N; int remain = len % R; int start = l % R; int end = (start + remain) % R; if (start <= end) { //[start,end) ans += sum[end] - sum[start]; } else { //[start,R)+[0,end) ans += sum[R] - sum[start] + sum[end]; } cout << ans << "\n"; } }