Editorial: Looking at Towers (easy version)

We count subsequences $a'$ of $a$ with $L(a') = L(a)$ and $R(a') = R(a)$, where $L$ and $R$ are the sets of heights visible from the left and right respectively (prefix maxima and suffix maxima).

The idea: handle the left constraint and right constraint independently with a DP, then combine them at the global maximum.

The prefix maxima of $a$ form a strictly increasing sequence $H = [H_0, H_1, \dots, H_{k-1}]$. A subsequence $a'$ satisfies $L(a') = L(a)$ if and only if its prefix maxima are exactly $\{H_0, \dots, H_{k-1}\}$.

Say a partial subsequence is at level $j$ if $H_j$ is the largest prefix max placed so far (running max $= H_j$). Then:

• An element with value $v \le H_j$ is a safe filler — including it doesn’t create a new prefix max. We can include or exclude it: factor $\times 2$.
• An element with value $H_{j+1}$ can advance the chain to level $j+1$.
• An element with value $v \in (H_j, H_{j+1})$ is forbidden at level $j$ — it would become a rogue prefix max.

Process elements $A_0, A_1, \dots, A_{n-1}$ left to right. Maintain an array $\mathrm{seg}[0..k{-}1]$ where $\mathrm{seg}[j]$ is the weighted count of partial subsequences at level $j$.

For each element $A_i$:

1. Let $\mathrm{id} = \text{lower\_bound}(H, A_i)$.
2. Filler: multiply $\mathrm{seg}[j]$ by 2 for all $j \ge \mathrm{id}$. These levels have running max $H_j \ge A_i$, so the element is a safe filler (include-or-exclude).
3. Advance: if $A_i = H_{\mathrm{id}}$, this element can start or extend the prefix max chain:
   • $\mathrm{dp}[i] = \begin{cases} 1 & \text{if } \mathrm{id} = 0 \\ \mathrm{seg}[\mathrm{id}-1] & \text{otherwise} \end{cases}$
   • $\mathrm{seg}[\mathrm{id}] \mathrel{+}= \mathrm{dp}[i]$.

Finally, zero out $\mathrm{dp}[i]$ for every position where $A_i \ne H_{k-1}$ (the global maximum). The surviving entries are what we need for combining with the right side.

Why the filler step is correct. At level $j$, the running max is $H_j$. An element with value $\le H_j$ is hidden behind that max and doesn’t become a prefix maximum. An element with value strictly between $H_{j-1}$ and $H_j$ can only be a filler at levels $\ge j$ — exactly the levels where seg gets multiplied.

Why the advance step is correct. An element $A_i = H_{\mathrm{id}}$ is strictly greater than $H_{\mathrm{id}-1}$ (the running max at level $\mathrm{id}-1$), so it becomes the new prefix max, advancing the chain to level $\mathrm{id}$. The number of ways to do so is exactly $\mathrm{seg}[\mathrm{id}-1]$ (all level-$(\mathrm{id}-1)$ subsequences that can be extended). For $\mathrm{id}=0$, we start a fresh chain.

Note that the filler step (×2 on $\mathrm{seg}[\mathrm{id}]$) also handles existing level-$\mathrm{id}$ subsequences including this element as a duplicate of the current max (not creating a new prefix max, just a repeat of $H_{\mathrm{id}}$). These two uses (filler-duplicate vs. advancing) are disjoint: one applies to already-level-$\mathrm{id}$ subsequences, the other to level-$(\mathrm{id}-1)$ subsequences.

Run the DP forward to get $L[i]$, and backward (reverse the array, run the same DP, reverse the result) to get $R[i]$. Both are nonzero only at positions where $A_i$ equals the global maximum $M$.

For two global-max positions $p \le q$:

• $L[p]$ accounts for all filler choices to the left of $p$ (within the left chain).
• $R[q]$ accounts for all filler choices to the right of $q$ (within the right chain).
• Between $p$ and $q$: every element has value $\le M$, so each of the $q - p - 1$ intermediate elements can be freely included or excluded $\to$ factor $2^{q-p-1}$.

Total answer:

This is computed in $O(n)$ with a single sweep:

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

At non-max positions $L[i] = R[i] = 0$, so cur simply doubles (accumulating the $2^{\text{gap}}$ factor). At a max position $i$, cur holds $\sum_{p < i} L[p] \cdot 2^{i-p-1}$, so (cur + L[i]) * R[i] captures all valid $(p, q)$ pairs with $q = i$.

The DP processes each element in $O(1)$ amortized if we use a naive array for the range multiply (acceptable for E1, $O(n^2)$ worst case) or $O(\log n)$ with a lazy segment tree (needed for E2, $O(n \log n)$). The combination sweep is $O(n)$.

$A = [4, 2, 4, 8, 3]$. Prefix maxima: $H = [4, 8]$. Global max $= 8$.

Left DP ($\mathrm{seg}$ has 2 entries for levels 0 and 1):

After zeroing non-max: $L = [0, 0, 0, 5, 0]$.

Right DP (reverse $A = [3, 8, 4, 2, 4]$, prefix maxima $H' = [3, 8]$):

After zeroing non-max: $\mathrm{dp}' = [0, 1, 0, 0, 0]$. Reverse back: $R = [0, 0, 0, 1, 0]$.

Combine: only position 3 has both $L$ and $R$ nonzero. $\mathrm{ans} = L[3] \cdot R[3] = 5 \cdot 1 = 5$. Matches expected output.