Hints: Looking at Towers (easy version)

Think about $L(a')$ and $R(a')$ separately first. What structure must a subsequence have so that $L(a') = L(a)$?

Compute $H = [H_0, H_1, \dots, H_{k-1}]$, the prefix maxima of $a$ (strictly increasing). A subsequence $a'$ has $L(a') = L(a)$ if and only if its own prefix maxima are exactly the same set of heights $\{H_0, H_1, \dots, H_{k-1}\}$.

Answer to Hint 1: For the prefix maxima of $a'$ to be exactly $H$:

• The subsequence must contain at least one element of each height $H_0, H_1, \dots, H_{k-1}$, appearing in order.
• It must not contain any element that would become a new prefix maximum with a height outside $H$.

When can an element with value $v$ become a “rogue” prefix max? When $v$ is strictly greater than all elements before it in the subsequence. So $v$ is safe (won’t create a new prefix max) if and only if the current running maximum of the subsequence is already $\ge v$.

This means: an element with value $v$ can be freely included or excluded only after a prefix max element of height $\ge v$ has been placed.

Answer to Hint 2: This suggests processing elements left to right and tracking which “level” of the prefix maxima chain we’ve reached. Define the level of a partial subsequence as the index $j$ such that $H_j$ is the largest prefix max placed so far.

At level $j$, the running maximum is $H_j$. So:

• Elements with value $\le H_j$ are safe fillers: they can be included or excluded freely (factor of 2 per filler).
• An element with value $H_{j+1}$ can advance us to level $j+1$.
• Elements with value in $(H_j, H_{j+1})$ cannot be included (they’d create a rogue prefix max), and they also can’t advance us.

Can you define a DP based on this?

Answer to Hint 3: Let $\mathrm{seg}[j]$ = the total number of valid partial subsequences currently at level $j$ (with all filler choices accounted for).

When processing element $A_i$ left to right:

1. Find $\mathrm{id} = \text{lower\_bound}(H, A_i)$, the first prefix max $\ge A_i$.
2. Filler step: For every level $j \ge \mathrm{id}$, we have $H_j \ge A_i$, so this element is a safe filler. Multiply $\mathrm{seg}[j]$ by 2 for all $j \ge \mathrm{id}$ (include-or-exclude choice).
3. Advance step: If $A_i = H_{\mathrm{id}}$ (it’s actually a prefix max value), then this element can advance subsequences from level $\mathrm{id}-1$ to level $\mathrm{id}$. The number of new level-$\mathrm{id}$ subsequences is $\mathrm{seg}[\mathrm{id}-1]$ (or 1 if $\mathrm{id} = 0$, starting a new chain). Add this to $\mathrm{seg}[\mathrm{id}]$.

Notice the filler step is a range multiply by 2, and the advance step is a point query + point update. For E1 ($n \le 5000$), a naive array suffices. What data structure would you use for E2?

Answer to Hint 4: For E2 ($n \le 3 \cdot 10^5$), use a lazy segment tree supporting range-multiply and point-query/point-update. Since $|H| \le n$, each element does $O(\log n)$ work, giving $O(n \log n)$ total.

At the end, $\mathrm{seg}[k-1]$ holds the total count of subsequences at the highest level — but we actually want something more fine-grained. Why?

Answer to Hint 5: We need to combine the left constraint ($L(a') = L(a)$) with the right constraint ($R(a') = R(a)$). These are not independent — the subsequence must satisfy both simultaneously.

The key observation: the global maximum $H_{k-1}$ must be present in the subsequence (it’s both the largest prefix max and the largest suffix max). So the global max acts as a “meeting point” between the left chain and the right chain.

Can you think about how to combine the left-side and right-side counts?

Answer to Hint 6: Run the same solve DP twice:

• Forward on the original array $\to$ array $L$, where $L[i]$ counts left-chain subsequences whose last advancing position (the one introducing the global max as a prefix max) is position $i$.
• Backward (reverse the array, run solve, reverse the result) $\to$ array $R$, where $R[i]$ counts right-chain subsequences whose last advancing position (for suffix maxima) is position $i$.

Both $L[i]$ and $R[i]$ are nonzero only at positions where $A_i$ equals the global maximum.

Now, how do you combine a left chain ending at position $p$ with a right chain starting at position $q$ (where $p \le q$ and both are global max positions)?

Answer to Hint 7: Consider two global max positions $p \le q$:

• $L[p]$ counts all filler choices for elements at positions $< p$ (between prefix max levels).
• $R[q]$ counts all filler choices for elements at positions $> q$ (between suffix max levels).
• Between positions $p$ and $q$: every element has value $\le$ the global max, so each of the $q - p - 1$ elements in between can be freely included or excluded. This gives a factor of $2^{q - p - 1}$.

If $p = q$ (same position serves as both the left and right advancing point), the factor is just $1$.

So the total answer is:

Answer to Hint 8: Computing this double sum naively would be $O(m^2)$ where $m$ is the number of global max positions. But it can be done in a single left-to-right sweep using a running variable $\mathrm{cur}$:

ans = 0, cur = 0
for i = 0 to n-1:
    ans += (cur + L[i]) * R[i]
    cur = cur * 2 + L[i]

At each position $i$:

• If $A_i$ is not the global max, $L[i] = R[i] = 0$, so ans doesn’t change and cur just doubles (absorbing the $\times 2$ factor for the gap).
• If $A_i$ is the global max, cur holds $\sum_{p < i} L[p] \cdot 2^{i - p - 1}$, so (cur + L[i]) * R[i] captures all pairs $(p, i)$ with $p \le i$.

Putting it all together — full algorithm:

1. Compute prefix maxima $H$ of $A$.
2. Run solve(A) using the level-DP with range-multiply $\to$ get $L[i]$.
3. Run solve(reverse(A)), then reverse the result $\to$ get $R[i]$.
4. Sweep left to right, combining $L$ and $R$ with the $\mathrm{cur}$ trick.

Complexity:

• E1 ($n \le 5000$): $O(n^2)$ with a naive array for the range multiply, or $O(n \log n)$ with a segment tree.
• E2 ($n \le 3 \times 10^5$): $O(n \log n)$ with a lazy segment tree.