type cursor = {
  p: (Z.t) array;
  mutable rank: Z.t;
  mutable last: bool;
  }

let create_cursor (n: Z.t) : cursor =
  let a = Array.make (Z.to_int n) Z.zero in
  (let o = Z.sub (Z.of_int (Array.length a)) Z.one in let o1 = Z.zero in
   let rec for_loop_to2 i =
     if Z.leq i o
     then begin a.(Z.to_int i) <- i; for_loop_to2 (Z.succ i) end
   in for_loop_to2 o1);
  { p = a; rank = Z.zero; last = Z.equal n Z.zero }

let has_next (c: cursor) : bool =
  if Z.leq (Z.of_int (Array.length c.p)) Z.one
  then begin c.last <- true; not c.last end
  else
    begin
      let r = ref (Z.of_string "-1") in
      (let t = ref (Z.sub (Z.of_int (Array.length c.p)) (Z.of_string "2")) in
       while Z.geq !t Z.zero do
         if Z.lt (c.p).(Z.to_int !t) (c.p).(Z.to_int (Z.add !t Z.one))
         then begin r := !t; t := Z.of_string "-1" end
         else t := Z.sub !t Z.one
       done);
      c.last <- Z.lt !r Z.zero;
      not c.last end

let swap (a: (Z.t) array) (i1: Z.t) (j: Z.t) : unit =
  let tmp = a.(Z.to_int i1) in
  a.(Z.to_int i1) <- a.(Z.to_int j); a.(Z.to_int j) <- tmp

let next (c: cursor) : (Z.t) array =
  if Z.equal c.rank Z.zero
  then begin c.rank <- Z.one; c.p end
  else
    begin
      if Z.gt (Z.of_int (Array.length c.p)) Z.one
      then
        let r = ref (Z.of_string "-1") in
        (let t = ref (Z.sub (Z.of_int (Array.length c.p)) (Z.of_string "2")) in
         while Z.geq !t Z.zero do
           if Z.lt (c.p).(Z.to_int !t) (c.p).(Z.to_int (Z.add !t Z.one))
           then begin r := !t; t := Z.of_string "-1" end
           else t := Z.sub !t Z.one
         done);
        if Z.lt !r Z.zero
        then begin c.last <- true; c.p end
        else
          begin
            (let j = ref (Z.sub (Z.of_int (Array.length c.p)) Z.one) in
             while Z.gt !j (Z.add !r Z.one) && Z.geq (c.p).(Z.to_int !r)
                                               (c.p).(Z.to_int !j) do
               j := Z.sub !j Z.one
             done;
             swap c.p !r !j);
            (let u = ref (Z.sub (Z.of_int (Array.length c.p)) Z.one) in
             let s = ref (Z.add !r Z.one) in
             while Z.geq !u Z.zero && Z.geq (Z.sub (Z.of_int (Array.length 
                                             c.p)) Z.one)
                                      !s && Z.gt !u !s do
               swap c.p !s !u; u := Z.sub !u Z.one; s := Z.add !s Z.one
             done);
            c.rank <- Z.add c.rank Z.one;
            c.last <- false;
            c.p
          end
      else begin c.last <- true; c.p end end

