Hints: Lost Civilization (Easy Version)
The generator starts from some initial sequence $x$ of length $m$ and repeatedly picks an index $i$, inserting $x_i+1$ immediately to the right of $x_i$, until the length reaches $m+k$. You are given the final array $a$ of length $n=m+k$.
Rephrase the task without guessing the steps: among all $x$ that could produce $a$, you want the smallest possible $m=|x|$. Try tiny examples—e.g. $[1,2,3,4,5]$ vs $[1,3,5,7,9]$—and ask how many values in $a$ “had to be there from the start” vs could have been created by inserts.
Answer to Hint 1: Inserts only ever add a value that is one more than some value already present, and they appear right next to that value. So if you read $a$ from right to left, the rightmost element of the current suffix is a natural candidate: either it was in the original $x$, or it is exactly $v+1$ sitting immediately after some $v$ to its left in the final array—meaning it could be “charged” to that $v$ and removed from the set of mandatory starters.
The hard part is deciding when that merge is legitimate in a shortest reconstruction, not just locally plausible.
Answer to Hint 2: Suppose the suffix you have already processed ends with value $t$. If $t = a_i + 1$ where $a_i$ is the value you are about to incorporate from the left, then $t$ can be interpreted as the number inserted right after $a_i$ in the forward process. In a minimal backward pass, you should treat that $t$ as not requiring its own root in $x$ once $a_i$ is present—you can discard $t$ and continue with $a_i$ as the next relevant rightmost value.
If this reminds you of “canceling” matching structure from the right, you are on the right track.
Answer to Hint 3: Maintain a stack of integers while scanning $i=n-1,n-2,\ldots,0$:
- While the stack is nonempty and the top equals $a_i+1$, pop (that top is absorbed as generated from $a_i$).
- Push $a_i$.
After the scan, output the stack size. Each stack entry is a value that still acts as an independent “root” that you cannot fold into anything farther right without contradicting minimality.
This is $O(n)$ per test case; only the stack operations matter.
Answer to Hint 4: Why is the final stack size equal to the minimum possible initial length? Sketch: any valid forward construction implies that whenever you see a local pattern that forces an insert after $v$ to explain $v+1$ on the right of $v$, you need at least one occurrence of $v$ in $x$ that is not “paid for” by a later insert. The stack algorithm is exactly the greedy backward pairing that removes every value that can be charged to a smaller neighbor to its left, and it is tight—no smaller set of survivors can be consistent with the insert rules.
A full formal proof is by induction on the suffix length, matching “last insert touching the suffix” with the pop rule.
Answer to Hint 5: Trace the algorithm on $[1,2,3,4,5]$: each new $a_i$ pops the previous top $a_{i+1}$, so only one value remains—answer $1$. On $[1,3,5,7,9]$ there is never an adjacent $+1$ pair, so nothing ever pops—answer $5$.
Try $[1,2,5,6,5]$ from the samples: watch when a pop happens and when equal values stack up; the answer should match the statement’s output.
Answer to Hint 6: Implementation details: use vector<int> stk (or deque); while (!stk.empty() && stk.back() == a[i] + 1) stk.pop_back(); then stk.push_back(a[i]);. Indices are $0$-based in code.
Avoid off-by-one: the condition compares stack top to current $a_i+1$, not $a_i$ to $a_{i+1}$ in the array (though those coincide when $a_{i+1}=a_i+1$ and the stack reflects the suffix).
Answer to Hint 7: Multiple test cases: clear the stack each test. The guarantee $\sum n \le 3\cdot 10^5$ makes the overall solution linear in total input size.
No modular arithmetic is required for A1; int is enough for values up to $10^9$ in comparisons, but stack holds int copies of array values.
Answer to Hint 8: If you still doubt the greedy rule, brute force for $n\le 8$: enumerate all sequences $x$ of small length over a small value range and simulate all legal insert sequences to see which $x$ can reach $a$, then compare the minimum $|x|$ to stk.size() on random $a$ produced by the forward process.
That experiment usually builds the right intuition faster than staring at the stack code alone—and it is the same $f(a)$ that A2 sums over all subsegments.