this it would follow $$d(t)-1=\max(l(M_t),p_{t-1},p_t)=\max(\max(l(M_t),p_{t-1}),\max(l(M_t),p_t)))=$$ $$=\max(d_1(t)-1,d_2(t)-1)<d(t)-1$$ and we obtain a contradiction.

Now, using this Lemma, we can introduce an algorithm that solves our problem working inductively. Given $\textbf{c} \in \mathbb{N}^r$, we want to compute $\textrm{Cond}(\textbf{c})$. We suppose that we are able to solve the problem for all $s<r$ and we develope a strategy for the $r$ case.

Let us fix some notations. If $k=2,\ldots,r-1$, we denote by $\textbf{c}_k=(c[1],\ldots,c[k])$ and by $\textbf{c}^k=(c[k+1],\ldots,c[r])$. Similarly, if $E=\left\{M_1,\ldots,M_r\right\}$, we denote by $E_k=\left\{M_1,\ldots,M_k\right\}$ and by $E^k=\left\{M_{k+1},\ldots,M_r\right\}.$ Furthermore for $i=1,\ldots,r-1$ we define the integers ${}^*p_i=\max(l(M_i),p_{i-1})$ and $p_i^*=\max(l(M_{i+1}),p_{i+1})$, where, by definition, we set $p_{r-1}^*=l(M_r)$ and ${}^*p_1=l(M_1)$.

Fixed $\textbf{c} \in \mathbb{N}^r$ we suppose to have a tree $T=T_{E}=(p_1,\ldots,p_{r-1}) \in \textrm{Cond}(\textbf{c})$ with $E=\left\{ M_1,\ldots,M_r \right\}$. Consider $t \in \left\{ 2,\ldots,r-1 \right\}$. It follows from the previous lemma that we only have two cases:\
$\bullet\ \textrm{Case}\  T_1=T_{E_t}=(p_1,\ldots,p_{t-1}) \in \textrm{Cond}(\textbf{c}_t).$

We clearly have $d_1(i)=d(i) $ for all $i=1,\ldots,t-1$, while from $T_1 \in \textrm{Cond}(\textbf{c}_t)$ it follows that $d_1(t)=d(t)$. Hence: $$^*p_t=\max(l(M_t),p_{t-1})=d_1(t)-1=d(t)-1=\max(p_t,p_{t-1},l(M_t))=\max(^*p_t,p_t)$$ and we deduce that $p_t \leq  {}^*p_t$.

We consider the tree $T_2=T_{E^t}=(p_{t+1},\ldots,p_{r-1})$, (if $t=r-1$ we have $T_2=M_r$). We clearly have $d_2(i)=d(i)$ for all $i=t+2,\ldots,r$.

On the other hand $d_2(t+1)-1=\max(l(M_{t+1}),p_{t+1})=p_{t}^*$ may be different from $$d(t+1)-1= \max(l(M_{t+1},p_{t+1},p_t)=\max(p_t^*,p_t).$$ Hence we have the following two subcases:\
