proposition: Lemma backwards_list_ind: forall A (P : list A -> Prop), P nil -> (forall (a : A) (l : list A), P l -> P (l +:: a )) -> forall l : list A, P l.
proof: Proof. intros. remember (length l). assert (Datatypes.length l <= n)%nat by lia. clear Heqn. revert l H1. induction n; intros. destruct l. apply H. simpl in H1. lia. remember (foot l). symmetry in Heqo. destruct o. 2: apply foot_none_nil in Heqo; subst l; apply H. apply foot_explicit in Heqo. destruct Heqo as [l' ?]. subst l. apply H0. apply IHn. rewrite app_length in H1. simpl in H1. lia. Qed.
imports: Coq.Lists.List Coq.micromega.Lia Coq.Sorting.Permutation Coq.ZArith.ZArith_base Coq.ZArith.Zcomplements Coq.Logic.FunctionalExtensionality CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext VST.zlist.sublist VST.zlist.list_solver