proposition: Lemma sorted_rev {A : Type}: forall (A_rel : A -> A -> Prop) (L : list A), Sorted A_rel L -> Sorted (Basics.flip A_rel) (rev L).
proof: Proof. intros. induction H. apply Sorted_nil. destruct l; simpl in *. repeat constructor. apply sorted_glue; auto. apply HdRel_inv in H0. apply H0. Qed.
imports: Psatz List Arith.Div2 Even Relations RelationClasses PeanoNat Peano_dec Recdef Sorting Permutation Multiset