[proofplan] We compare the first row of the insertion tableau with the standard minimal-tail data for weakly increasing subsequences. After each prefix of the word, the $k$-th first-row entry will be the smallest possible terminal value of a weakly increasing subsequence of length $k$ in that prefix. This invariant is proved directly by induction, using exactly the same strict-greater replacement rule as row insertion. Since such a terminal value exists precisely for the attainable subsequence lengths, the number of first-row entries is the maximum length of a weakly increasing subsequence. [/proofplan] [step:Define the prefix tableaux and their first rows] For each integer $m$ with $0\le m\le n$, let $w_{\le m}=w_1\cdots w_m$ denote the prefix of length $m$, with $w_{\le 0}$ the empty word. Let $P_m:=P(w_{\le m})$ be the tableau obtained after inserting the first $m$ letters. Let $\ell_m\in \mathbb N\cup\{0\}$ be the length of the first row of $P_m$, and write that first row as \begin{align*} r_{1,m},r_{2,m},\dots,r_{\ell_m,m}. \end{align*} By the definition of the row insertion procedure, inserting $a:=w_m$ into $P_{m-1}$ changes the first row by replacing the leftmost entry $r_{j,m-1}$ satisfying $r_{j,m-1}>a$, if such an entry exists, and otherwise by appending $a$ to the end of the first row. Entries bumped from the first row affect only lower rows and therefore do not alter this description of the first-row update. [/step] [step:Introduce finite minimal tails for weakly increasing subsequences] For each $m$ and $k$, define $E_{k,m}\subset A$ to be the set of terminal letters of weakly increasing subsequences of length $k$ in $w_{\le m}$: \begin{align*} E_{k,m}=\{w_{i_k}:1\le i_1<\cdots<i_k\le m \text{ and } w_{i_1}\le\cdots\le w_{i_k}\}. \end{align*} Let $L_m$ be the maximum length of a weakly increasing subsequence of $w_{\le m}$, with $L_0=0$. For $1\le k\le L_m$, the set $E_{k,m}$ is finite and nonempty, so its minimum exists in the finite totally ordered set $E_{k,m}$. Define \begin{align*} \tau_{k,m}:=\min E_{k,m}. \end{align*} No well-ordering of $A$ is used here; the minimum is taken over a finite nonempty set. [/step] [step:Prove that minimal tails obey the strict-greater replacement rule] We prove by induction on $m$ that the finite list \begin{align*} \tau_{1,m},\tau_{2,m},\dots,\tau_{L_m,m} \end{align*} is updated from the previous list by replacing the leftmost entry strictly greater than $w_m$, or appending $w_m$ if no such entry exists. We first record the monotonicity of this list. For any fixed prefix length $s$ and any integer $j$ with $1\le j<L_s$, choose a weakly increasing subsequence of length $j+1$ in $w_{\le s}$ whose terminal letter is $\tau_{j+1,s}$. Its first $j$ selected letters form a weakly increasing subsequence of length $j$ whose terminal letter is at most $\tau_{j+1,s}$. Since $\tau_{j,s}$ is the minimum terminal letter among all length-$j$ weakly increasing subsequences in $w_{\le s}$, we obtain \begin{align*} \tau_{j,s}\le \tau_{j+1,s}. \end{align*} Thus the minimal-tail list is weakly increasing wherever it is defined. For $m=0$, both the list of minimal tails and the first row are empty. Assume the assertion for $m-1$, and put $a:=w_m$ and $L:=L_{m-1}$. If $L=0$, then the only weakly increasing subsequence of positive length in $w_{\le 1}$ has length $1$ and terminal letter $a$, so the list becomes $(a)$. Now suppose $L\ge 1$. Let $q$ be the smallest index $1\le q\le L$ such that $\tau_{q,m-1}>a$, if such an index exists. If no such index exists, set $q:=L+1$. First assume $q\le L$. For every $k<q$, we have $\tau_{k,m-1}\le a$ by the definition of $q$. A new weakly increasing subsequence of length $k$ ending at the newly inserted letter $a$ cannot lower the minimal terminal value below $\tau_{k,m-1}$, because its terminal value is $a\ge \tau_{k,m-1}$. Hence \begin{align*} \tau_{k,m}=\tau_{k,m-1} \end{align*} for $1\le k<q$. For $k=q$, if $q=1$, the one-letter subsequence $(a)$ shows that $a\in E_{1,m}$. If $q>1$, then $\tau_{q-1,m-1}\le a$, so there exists a weakly increasing subsequence of length $q-1$ in $w_{\le m-1}$ ending at $\tau_{q-1,m-1}$; appending the final letter $a$ gives a weakly increasing subsequence of length $q$ in $w_{\le m}$ ending at $a$. Thus $\tau_{q,m}\le a$. Since $\tau_{q,m-1}>a$, this shows the minimal tail at position $q$ is lowered at most to $a$. It remains to show that it cannot be lowered below $a$. Any weakly increasing subsequence in $w_{\le m}$ of length $q$ either avoids the new letter $a$, in which case its terminal letter is at least $\tau_{q,m-1}>a$, or uses the new letter $a$, in which case its terminal letter is exactly $a$. Therefore \begin{align*} \tau_{q,m}=a. \end{align*} For $k>q$, a new weakly increasing subsequence of length $k$ using the letter $a$ would require a weakly increasing subsequence of length $k-1$ in $w_{\le m-1}$ ending at a letter at most $a$. But $k-1\ge q$, so every terminal letter of a weakly increasing subsequence of length $k-1$ is at least $\tau_{k-1,m-1}\ge \tau_{q,m-1}>a$. Hence no such new subsequence exists, and the minimal tails for $k>q$ are unchanged. If instead $q=L+1$, then $\tau_{L,m-1}\le a$. Appending $a$ to a weakly increasing subsequence of length $L$ ending at $\tau_{L,m-1}$ gives a weakly increasing subsequence of length $L+1$ in $w_{\le m}$, so $L_m=L+1$ and $\tau_{L+1,m}=a$. For $1\le k\le L$, any new subsequence of length $k$ ending at $a$ has terminal value $a\ge \tau_{k,m-1}$, so the existing minimal tail remains minimal. Thus the update is exactly append $a$. [guided] The key point is that the first row update uses the phrase "leftmost entry strictly greater than $a$." We now prove that the minimal-tail data for weakly increasing subsequences uses exactly the same rule. First, the minimal tails are weakly increasing in the subsequence length. For any fixed prefix length $s$ and any integer $j$ with $1\le j<L_s$, choose a weakly increasing subsequence of length $j+1$ in $w_{\le s}$ whose terminal letter is $\tau_{j+1,s}$. Its first $j$ selected letters form a weakly increasing subsequence of length $j$ whose terminal letter is at most $\tau_{j+1,s}$. Since $\tau_{j,s}$ is the minimum possible terminal letter for length $j$, we have \begin{align*} \tau_{j,s}\le \tau_{j+1,s}. \end{align*} This monotonicity is the reason that once a tail is strictly greater than $a$, all later tails are also strictly greater than $a$. Fix a prefix length $m\ge 1$, and write $a:=w_m$. Assume that after $m-1$ letters we know the minimal possible final letters \begin{align*} \tau_{1,m-1},\tau_{2,m-1},\dots,\tau_{L,m-1}, \end{align*} where $L=L_{m-1}$. The value $\tau_{k,m-1}$ means: among all weakly increasing subsequences of length $k$ in the first $m-1$ letters, this is the smallest possible last letter. Let $q$ be the first index such that $\tau_{q,m-1}>a$. If there is no such index, set $q=L+1$. We examine what subsequences become possible after the new letter $a$ is appended to the word. For lengths $k<q$, the definition of $q$ gives $\tau_{k,m-1}\le a$. If a new subsequence of length $k$ uses the new letter, its terminal letter is $a$, and this is not smaller than the old best terminal value $\tau_{k,m-1}$. Therefore the new letter cannot improve the minimal tail for any $k<q$, so \begin{align*} \tau_{k,m}=\tau_{k,m-1} \end{align*} for $1\le k<q$. At length $q$, the new letter does improve the minimal tail. If $q=1$, the one-letter subsequence consisting of $a$ itself has terminal letter $a$. If $q>1$, then $\tau_{q-1,m-1}\le a$, so there is a weakly increasing subsequence of length $q-1$ ending at $\tau_{q-1,m-1}$; appending the new final letter $a$ gives a weakly increasing subsequence of length $q$ ending at $a$. Thus $\tau_{q,m}\le a$. Why is $a$ the smallest possible terminal value at length $q$? A length-$q$ subsequence in the new prefix either avoids the new letter or uses it. If it avoids the new letter, then it already existed in $w_{\le m-1}$, so its terminal letter is at least $\tau_{q,m-1}$, and by the choice of $q$ this is strictly greater than $a$. If it uses the new letter, its terminal letter is exactly $a$. Hence no terminal value below $a$ can occur, and \begin{align*} \tau_{q,m}=a. \end{align*} For lengths $k>q$, the new letter cannot create a better terminal value. Indeed, a new weakly increasing subsequence of length $k$ ending at $a$ would need a weakly increasing subsequence of length $k-1$ in the previous prefix ending at a value at most $a$. But $k-1\ge q$, so every terminal value of such a length-$k-1$ subsequence is at least $\tau_{k-1,m-1}$, and monotonicity of the minimal-tail list gives $\tau_{k-1,m-1}\ge\tau_{q,m-1}>a$. Therefore no such predecessor can be extended by $a$, and the tails beyond $q$ remain unchanged. Finally suppose there is no index $q\le L$ with $\tau_{q,m-1}>a$. Then $\tau_{L,m-1}\le a$, so a longest weakly increasing subsequence in the previous prefix can be extended by $a$. This creates a subsequence of length $L+1$ ending at $a$. For every old length $k\le L$, the new terminal value $a$ is at least $\tau_{k,m-1}$, so it cannot improve the old minimal tail. Hence the update is precisely to append $a$. [/guided] [/step] [step:Identify the first row with the minimal-tail list] The first row of $P_0$ and the minimal-tail list for $w_{\le 0}$ are both empty. By the first step, the first row is updated at stage $m$ by replacing the leftmost entry strictly greater than $w_m$, or appending $w_m$ if no such entry exists. By the previous step, the minimal-tail list is updated by the same rule. Induction on $m$ gives \begin{align*} \ell_m=L_m \end{align*} and \begin{align*} r_{k,m}=\tau_{k,m} \end{align*} for every $1\le k\le \ell_m$. [/step] [step:Read off the first part of the shape] Taking $m=n$, the number $\ell_n$ is the length of the first row of $P(w)$. Since the shape of $P(w)$ is $\lambda=(\lambda_1,\lambda_2,\dots)$, this first-row length is $\lambda_1$. The preceding step gives $\ell_n=L_n$, and by definition $L_n$ is the maximum length of a weakly increasing subsequence of the full word $w$. Therefore \begin{align*} \lambda_1=\max\{k \in \mathbb N : \text{there exist } 1\le i_1<\cdots<i_k\le n \text{ with } w_{i_1}\le\cdots\le w_{i_k}\}. \end{align*} This is the desired statement. [/step]