Hints: Lost Civilization (Hard Version)

Let $f(b)$ be the minimum initial length for the insert process to produce the array $b$ (the easy version). The hard version asks for $$T ;=; \sum_{0\le l\le r<n} f\bigl([a_l,\ldots,a_r]\bigr).$$

Partition by right endpoint. Every subsegment has a unique index $r$ where it ends. Define $$S(r) ;=; \sum_{l=0}^{r} f\bigl([a_l,\ldots,a_r]\bigr),$$ the total contribution of all subsegments that end at position $r$. Then $$T ;=; S(0) + S(1) + \cdots + S(n-1).$$

So instead of a messy double sum over $(l,r)$, you can think: for each $r$, sum $f$ over every left end $l\le r$; then add those row sums.

Nothing here assumes a particular implementation—only combinatorics.

Answer to Hint 1: Easy version (brute force, $O(n^3)$). There are $\Theta(n^2)$ pairs $(l,r)$. For each pair, take the subarray of length $m=r-l+1$ and run the A1 stack (right-to-left pops while top == a[i]+1, then push a[i]); the stack size is $f([a_l..a_r])$. One evaluation costs $O(m)$, and $\sum_{l\le r}(r-l+1)=O(n^3)$ over all pairs, so the whole test case is cubic in $n$.

This is correct and good for tiny $n$ (e.g. stress-testing or understanding samples), but it will not pass the contest limits.

Answer to Hint 2: Easier improvement: all subsegments inside a prefix ($O(n^2)$). For a fixed $r$, you only care about the prefix $a[0..r]$. Let $$T(r) ;=; \sum_{0\le l\le r’\le r} f\bigl([a_l,\ldots,a_{r’}]\bigr),$$ the same kind of total as in the full problem, but restricted to subsegments that lie entirely in indices $0..r$.

When you increase $r$ by one, the new subsegments are exactly those whose right end is $r$ (the new index). Their total is precisely $S(r)$ from Hint 1. Moreover $$T(r) = T(r-1) + S(r) \quad (r\ge 1), \qquad T(-1)=0.$$ So $S(r) = T(r) - T(r-1)$ and $T(n-1)=T$ is the final answer.

If you can compute $T(r)$ in $O(r)$ time for each $r$, then computing $T(0),T(1),\ldots,T(n-1)$ costs $O(0+1+\cdots+(n-1))=O(n^2)$ per test case—a natural “medium” step between brute force and the linear solution.

Answer to Hint 3: How to get $T(r)$ in one $O(r)$ backward pass. Temporarily forget the global $n$ and work only on indices $0..r$. Run the same right-to-left stack rule as A1, but store pairs $(\text{value},\text{weight})$ and maintain an integer res (64-bit):

• Scan $i=r,r-1,\ldots,0$.
• While the stack is nonempty and stk.back().first == a[i] + 1, subtract stk.back().second from res, then pop.
• Push (a[i], (r+1) - i) — i.e. weight (r - i + 1), the number of left indices $l$ with $i\le l\le r$ (all choices of $l$ in the current suffix that can still pair with a subsegment ending somewhere in $i..r$ in the bookkeeping used by this construction).
• Add res to a local accumulator ans_r after each $i$ (same pattern as the model solution, but with r+1 in place of n).

At the end of this inner loop, ans_r equals $T(r)$. (Check: $r=0$ gives $f([a_0])$; $r=1$ reproduces the sum over the three subsegments of length $\le 2$.)

Repeating for every $r$ yields an $O(n^2)$ algorithm; the final answer is $T(n-1)$ from the last run—you do not need to add all $T(r)$ unless you are verifying the identity $T=\sum_r S(r)$ by differencing $T(r)-T(r-1)$.

Answer to Hint 4: What res means when the right border is fixed at $r$. After you have processed indices $i,i+1,\ldots,r$ (i.e. you are about to move left past $i-1$), res is set up so that it tracks the sum of $f$ over all subsegments that end at $r$ and whose left endpoint lies in ${i,i+1,\ldots,r}$—the family of “still active” pairs $(l,r)$ with $l\ge i$.

When you pop because top == a[i]+1, you remove from res exactly the contribution tied to stack levels that merge into $a_i$ under the same rule as in A1, so the partial sums stay aligned with the true values of $f$ on those suffixes.

Thus each inner pass is not “magic”: it is the weighted extension of the easy stack, specialized to the prefix $0..r$ with last index $r$ as the distinguished right end for the weight $(r-i+1)$.

Answer to Hint 5: From $O(n^2)$ to $O(n)$ (contest solution). The expensive part of the $O(n^2)$ approach is restarting the scan for every $r$. Observe that when you go from prefix $0..(r-1)$ to $0..r$, you append one new element on the right; the backward merge structure changes in a way that can be updated incrementally if you do not throw away the whole state.

The linear algorithm is exactly that: a single sweep $i=n-1,\ldots,0$ on the full array, with weight (n - i) (the count of left endpoints $l$ with $i\le l\le n-1$ for subsegments that end at the global last index $n-1$), and ans += res at every $i$. One pass, $O(n)$.

Intuitively, each step folds in contributions for all right endpoints at once via the running res and the accumulated ans; the algebra is set up so the total still equals $\sum_r S(r)=T$, without computing each $S(r)$ explicitly.

Answer to Hint 6: Dual bookkeeping (optional but clarifying). Besides $T=\sum_r S(r)$, the same total admits a left-heavy form. If after processing index $i$ (in the global $O(n)$ scan) res equals $\sum_{l=i}^{n-1} f([a_l..a_{n-1}])$, then $$\sum_{i=0}^{n-1} \texttt{res}i ;=; \sum{l=0}^{n-1} (l+1),f\bigl([a_l..a_{n-1}]\bigr).$$ For this problem that double sum matches $T$ (you can verify on samples such as $[1,2,3,4,5]$ and $[1,3,5,7,9]$). So the linear code is simultaneously: (i) accumulating row sums $S(r)$ in a folded way, and (ii) equivalent to a weighted sum of “full suffix” $f$ values by left end.

You do not need this identity to implement the solution; it only explains why ans += res every step is not the same as “output res once at $i=0$”.

Answer to Hint 7: Implementation checklist (global $O(n)$). vector<pair<int,int>> stk, i64 res = 0, ans = 0. For i from n-1 down to 0: pop while stk.back().first == a[i] + 1, subtracting second from res; push (a[i], n - i); res += n - i; ans += res. Print ans. Use 64-bit integers; no modulus.

Sanity: $[1,2,3,4,5]$ has $f=1$ on every nonempty subsegment, and there are $n(n+1)/2=15$ of them, so ans = 15. For $[1,3,5,7,9]$ (length $5$), $f([l..r])=r-l+1$, and the sum is $35$ as in the statement.

Answer to Hint 8: Debugging path. If the linear answer is wrong, first check A1 on random subarrays. Then implement the $O(n^2)$ “compute $T(r)$ per $r$” method from Hint 4 and compare to the linear program on random $n\le 200$. Once they match, you know the bug is only in the single-pass aggregation.

Multi-test: clear stk, res, ans per case; rely on $\sum n$ bounded for total time.