proposition: Lemma NoDup_app_bwd : forall A (ls1 ls2 : list A), NoDup (ls1 ++ ls2) -> NoDup ls1 /\ NoDup ls2 /\ (forall x, In x ls1 -> ~In x ls2).
proof: Proof. induction ls1; simpl; eauto; inversion 1; subst. apply IHls1 in H3; intuition (subst; eauto using in_or_app). constructor; intuition eauto using in_or_app. Qed.
imports: Coq(FunctionalExtensionality Arith Lia) Coq(Arith.Peano_dec Arith.Compare_dec) Coq(Relations.Relation_Operators) Coq(List) Chapar(Predefs)