open Printf
open Scanf

let solve rr la l r =
  let f x a = if x < a then 0 else (x - a) / rr + 1 in
  List.map (fun a -> f r a - f (l - 1) a) la |> List.fold_left (+) 0

let () =
  let id x = x in
  scanf "%d %d " (fun rr n ->
      let la = List.init n (fun _ -> scanf "%d " id) in
      let q = scanf "%d " id in
      let rec loop i =
        if i = 0 then ()
        else begin
            scanf "%d %d " (fun l r -> printf "%d\n" @@ solve rr la l r) ;
            loop (i - 1)
          end in
      loop q
    )