proposition: Lemma Permutation_incl_cons_inv_r (l1 l2 : list A) a : incl l1 (a :: l2) -> exists n l3, Permutation l1 (repeat a n ++ l3) /\ incl l3 l2.
proof: Proof. induction l1 as [|b l1 IH]. - intros _. now exists 0, nil. - intros [Hb Hincl] %incl_cons_inv. destruct (IH Hincl) as [n [l3 [Hl1 Hl3l2]]]. destruct Hb. + subst b. exists (S n), l3. eauto. + exists n, (b :: l3). eauto using incl_cons. Qed.
imports: List Setoid Compare_dec Morphisms FinFun PeanoNat