let scan_int () = Scanf.scanf " %d" (fun x -> x)
let print_int n = Printf.printf "%d\n" n
let scan_array len read_func = Array.init len (fun _ -> read_func())

(* zero-based numbering *)
module SegmentTree :
  sig
    type 'a st
    val init   : int -> ('a -> 'a -> 'a) -> 'a -> 'a st
    val set    : 'a st -> int -> 'a -> unit
    val build  : 'a st -> unit
    val update : 'a st -> int -> 'a -> unit
    val query  : 'a st -> int -> int -> 'a
    val get    : 'a st -> int -> 'a
  end =
  struct
    type 'a st = {n: int; func: ('a -> 'a -> 'a); seg: 'a array; id: 'a}
    let get_n _n =
      let rec loop n ret = if ret < n then loop n (ret*2) else ret in loop _n 1
    let init _n _func _id =
      let _n = get_n _n in {n = _n; func = _func; seg = Array.make (_n*2) _id; id = _id}
    let set st i x = st.seg.(st.n+i) <- x
    let merge st par = st.seg.(par) <- st.func st.seg.(par*2) st.seg.(par*2+1)
    let build st =
      let rec loop i = 
        if i = 0 then () else let _ = merge st i in loop (i-1) in
      loop (st.n-1)
    let update st i x =
      let _ = set st i x in
      let k = i + st.n in
      let rec loop i =
        if i = 0 then () else let _ = merge st i in loop (i/2) in
      loop (k/2)
    (* query: [a, b) *)
    let query st a b =
      let rec loop a b l r =
        if a >= b then st.func l r
        else
          let l = if a land 1 = 0 then l else st.func l st.seg.(a) in
          let r = if b land 1 = 0 then r else st.func st.seg.(b-1) r in
          loop ((a + a land 1) / 2) ((b - b land 1) / 2) l r in
      loop (a+st.n) (b+st.n) st.id st.id
    let get st i = st.seg.(st.n+i)
  end

let f x (a, list) = if (List.hd list < x) then (a+1, x :: list) else (a, list)

let merge (a, a_list) (b, b_list) = List.fold_right f b_list (a, a_list)

let () =
  let n = scan_int() and q = scan_int() in
  let st = SegmentTree.init n merge (0, [0]) in
  let _ =
    for i = 0 to n-1 do
      let a = scan_int() in
      SegmentTree.set st i (1, [a])
    done in
  let _ = SegmentTree.build st in
  for i = 1 to q do
    let op = scan_int() and l = scan_int() and r = scan_int() in
    let ans, _ = SegmentTree.query st (l-1) r in
    print_int ans
  done