Number of chains

This is from paper Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme by Hart and Sharir, section 4.1.

A sequence of integers $U=(u_1,u_2,\ldots)$ does not contain  (not necessarily contiguous) subsequence $xyxyx$ where $x\neq y$. $u_j\in\{1,2,\ldots,n\}$ for each $j$. Moreover, for $k=1,2,\ldots,n-1$, the first appearance of $k$ precedes that of $k+1$. Finally, no two consecutive integers are identical.

Define a chain as a maximal decreasing contiguous subsequence of $U$.

Lemma. $U$ has at most $2n$ chains.

===================================

Proof:

We will modify $U$ which may or may not reduce its chains. Let $a<b<c<\ldots$ be integers in $\{1,2,\ldots,n\}$, which may not be consecutive.

Observation 1. $U$ does not have consecutive subsequences $cba$ and $bac$.

Proof: If it has $cba$, remove $b$. If it has $bac$, remove $a$. $\square$

Let $I=(i_1,i_2,\ldots)\subset U$ be the maximal leading subsequence of $U$ where $i_j=j$ for each $i_j\in I$.

Observation 2. $I$ does not end with $c$ followed by $ab$.

Proof: If it does, $U$ has $abcab$ and no more $a$ thereafter. We can then remove $a$'s, reduce $n$ by $1$, and reduce the number of chains by $2$. $\square$

Observation 3. $I$ does not end with $b$ followed by $ab$.

Proof: If it does, $U$ has $abab$ and no more $a$ thereafter. We can remove $a$'s and the second $b$, reduce $n$ by $1$, and reduce the number of chains by $2$. $\square$

Eventually, we arrive at $U$ with $I=(1,2,3,\ldots,n)$ followed by one or no integer. It has $n\leq 2n$ chains.

$\square$