let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let abs = Array.init m @@ fun _ ->
    Scanf.scanf "%d %d\n" @@ fun a b -> a, b in
  let counts = Array.make (2 * n) 0 in
  Array.iter (fun (a, b) ->
    counts.(2 * b - 2) <- counts.(2 * b - 2) - 1;
    counts.(2 * a - 1) <- counts.(2 * a - 1) + 1) abs;
  for i = 1 to 2 * n - 1 do
    counts.(i) <- counts.(i) + counts.(i - 1)
  done;
  Printf.printf "%d\n" @@ fst @@ snd @@ 
  Array.fold_left (fun (c, (acc, dir)) c' ->
    c',
    if dir = 0 then (acc, compare c c')
    else if compare c c' = 0 || dir = compare c c' then (acc, dir)
    else if c > c' then (1 + acc, compare c c')
    else (acc, compare c c')) (counts.(0), (0, 0)) counts
  

