Lost Civilization (Easy Version)

Research checked: the official statement, the official contest editorial page, and Codeforces discussion on that editorial page mentioning stack, DP, and interval-style solutions. The public editorial text currently exposes only a placeholder for 2201A1, so the statement is the source of truth here.

Model one original input element as a root. Every value inserted from it is a descendant, and all descendants of that root stay in one contiguous block of the final sequence. So the final array is a sequence of blocks, one block per original input element.

Now look inside one block. Reading it left to right is like a DFS preorder of a rooted tree where every child has value parent $+1$. While reading, keep the active path: nodes whose subtrees have not been closed yet. A new value $x$ can belong to the current block exactly when some active node has value $x-1$. Then $x$ becomes a child of that node, and any deeper active nodes are closed.

The nice trick: the active path values are always consecutive. If the current block started at value $L$ and the current top value is $R$, then the active labels are exactly

$[L,R]$.

Initially a new block has interval $[x,x]$. For the next value $x$:

• If $x-1 \in [L,R]$, then $x$ can be generated. We pop back to $x-1$ and push $x$, so the active interval becomes $[L,x]$.
• If $x-1 \notin [L,R]$, then the current block cannot generate $x$. This is not negotiable; $x$ must be a new original input element. Increment the answer and reset to $[x,x]$.

This also explains the common wrong idea: checking whether $x-1$ appeared somewhere before is not enough. In $[1,2,3,2,4]$, the value $3$ appeared before $4$, but after reading the second $2$, that old $3$ is no longer active. It is closed. Dead parent, dead plan.

Proof of correctness:

First, the interval invariant is true. At the start of a block, the active path contains only the root, so it is $[L,L]$. If we attach $x$ under active value $x-1$, all values above $x-1$ close and $x$ becomes the new top, leaving exactly $[L,x]$. If no such parent exists, a new block starts at $x$, giving $[x,x]$.

Second, every time the algorithm starts a new block, that new original element is forced. Assume all previous starts found by the algorithm are forced. Between the last forced start and the current position, the active interval is deterministic by the invariant. If $x-1$ is outside it, then no unfinished node in the current block can generate $x$. Older blocks are already closed and cannot receive new elements. Therefore any valid input sequence must include $x$ itself as a new original element.

Third, whenever $x-1$ is inside the interval, attaching $x$ is valid and uses no new original element. Starting a new block there would only add an unnecessary root, which is how you donate points to the problemsetter for free.

So the algorithm counts exactly the forced original elements, and that count is the shortest possible input length.

Complexity is $O(n)$ per test case and $O(1)$ extra memory. Over all tests this is $O(\sum n)$, easily within the limits.