Lexicographic Partition

The annoying part is that $f$ is not asking for the number of blocks in some random optimal partition. The lexicographic maximum forces a very specific chain of starting positions. Once you see that chain, the problem turns into a tree construction.

Computing the optimal chain

Take a prefix $p_1,p_2,...,p_m$, and suppose the current segment starts at position $l$.

Let $r$ be the first position after $l$ with $p_r < p_l$. If there is no such position, pretend $r=m$ for the allowed range.

The first minimum in the answer should be as large as possible. We can always make it $p_l$ by starting the block at $l$, but if the block includes the first smaller element, the minimum drops below $p_l$, which is instantly worse. So the first block must end before that first smaller element.

After fixing the first output value as $p_l$, we choose where the next block starts. If it starts at $q$, then the next output value starts with $p_q$. So among all legal next starts, we choose the position with maximum value. Then we repeat from there.

So the optimal sequence is a chain of indices:

• start at $1$;
• from $l$, jump to the maximum value in the legal range after $l$;
• stop only when we reach the end of the prefix.

That last bullet matters: for any prefix of length $m$, the chain always ends at index $m$. Therefore $f$ is exactly the length of this chain.

The false assumption is that appending one element only increases the answer by $0$ or $1$. Nope. A very large new value can make an early chain node jump straight to the end and delete a bunch of old chain nodes from the optimal answer. That is where the problem earns its 3500 tax.

Turning $x$ into a tree

If $x_i=k$, then in the optimal chain for prefix $i$, index $i$ is the last node and its predecessor has chain length $k-1$.

More specifically, the predecessor is the latest earlier index $j<i$ with $x_j=k-1$. If a later such index existed, the jump rule would prefer that later candidate structure instead. So each index $i>1$ gets a parent:

$parent(i) =$ latest $j<i$ such that $x_j=x_i-1$.

Now $x$ is a preorder depth list of a rooted tree:

• vertex $1$ is the root at depth $1$;
• vertex $i$ has depth $x_i$;
• its parent is the latest previous vertex at depth $x_i-1$.

Immediate impossible cases:

• $x_1$ is not $1$;
• some later $x_i=1$;
• $x_i > x_{i-1}+1$, because a preorder depth sequence cannot jump down into nowhere;
• the needed previous depth $x_i-1$ does not exist.

The real obstruction

Call a node branching if it has at least two children.

A branching node cannot have a branching child.

Why? Suppose node $u$ has multiple children. For the chain to jump from $u$ to its next child, that child root must beat everything relevant before it. This forces the child roots of $u$ to behave like increasing maxima, and values in those child areas must stay above $p_u$.

Now if one child $v$ also branches, its own children force the same kind of increasing-maxima behavior below $v$. Then a later grandchild becomes larger than $v$ while still being visible from $u$. The jump from $u$ would go too deep, skipping $v$, so the depth sequence collapses. The classic tiny disaster is $[1,2,2,3,3]$: it forces comparisons like $p_1<p_2<p_3$ and $p_3<p_4<p_5$, so everything becomes one increasing run, giving the wrong $x$.

So the tree is valid exactly when no branching node has a branching child.

Constructing the permutation

We recursively assign a consecutive value interval to each subtree. The subtree of a node is contiguous because the indices are preorder labels.

For a subtree rooted at $u$, suppose all still-unassigned values for descendants are in $[lo,hi]$, and $p_u$ is already assigned.

There are two cases.

Case 1: $u$ has one child $v$.

There is no sibling competition, so the chain from $u$ only needs to go to $v$. If $v$ is branching, give $v$ the smallest remaining value, because a branching node wants to be the minimum of its own subtree. Otherwise, give $v$ the largest remaining value, which keeps chains simple. Then recurse on $v$.

Case 2: $u$ has multiple children.

Then $u$ must be the minimum of its subtree. If this node was forbidden to branch, we fail.

Give the direct children the largest available values, increasing from left to right. Give each child subtree a consecutive block of the smaller remaining values. Then recurse into every child, marking those children as not allowed to branch. This exactly enforces the no branching child of a branching node rule.

For the root:

• if it has multiple children, set $p_1=1$;
• otherwise set $p_1=n$.

The recursive interval assignment uses every number exactly once, so the output is a permutation. The induction proof follows the construction: single-child nodes have only one possible next tree step, and branching nodes see their direct child roots as the left-to-right maxima, while descendants are kept below those roots.

Everything is linear: build the tree in $O(n)$, assign values in $O(n)$, done.