Flatten or Concatenate

First, deconstruct the trap: this is interactive, but we are not trying to reconstruct the array. That would be massive overkill. We only need the maximum, and the operation history leaves enough structure to chase it with interval sums.

The invariant

Flattening one element $x$ into two copies of $x/2$ preserves the sum of that array.

Concatenation sets both arrays to $a+b$. Since $a$ and $b$ always had equal sums before the operation, the new array sum is exactly twice the old sum.

So every relevant array has a power-of-two total sum, and more importantly, whenever an array is split by its top-level construction, the two pieces have equal sum.

The hidden recursive shape

Think of a generated array as leaves of a binary structure.

A piece of total sum $S$ can be split into two consecutive pieces of sum $S/2$ in either of two ways:

• by flattening one value $S$ into two values $S/2$;
• by concatenating two arrays whose sums were both $S/2$.

After that split, later flatten operations only happen inside one side or the other. They preserve that side's sum and do not move elements across the boundary.

Therefore, for any generated interval with total sum $S$ and length greater than $1$, there is an index $m$ such that

$$\sum_{i=l}^{m} a_i = \frac S2.$$

Because all $a_i$ are positive, prefix sums strictly increase, so this index is unique. Nice. The problem just handed us a binary-search target and tried to look mysterious about it.

Finding the split

Suppose we are currently solving interval $[l,r]$ and we know its total sum is $S$.

We binary search the smallest position $m$ such that

$$\sum_{i=l}^{m} a_i \ge \frac S2.$$

Validity of the hidden array guarantees the sum is exactly $S/2$ at that position. Querying interval sums gives each binary-search comparison.

Now $[l,m]$ and $[m+1,r]$ both have total sum $S/2$.

Why the shorter half contains the maximum

This is the key bit.

At the moment the two halves became separate, they came from the same state:

• after a flatten split, both halves started as the same single value $S/2$;
• after a concatenate split, the two arrays were equal at the previous synchronization point, then only flatten operations happened independently before they were concatenated.

From the same starting array, every flatten operation increases length by exactly $1$ and never increases the maximum. It either leaves the maximum unchanged because other maximum elements remain, or it cuts the maximum in half. Either way, more flattening cannot make the maximum larger.

So the side with smaller length was flattened fewer times, and its maximum is at least the other side's maximum. That means it contains a maximum of the whole interval. If the lengths are equal, both sides have gone through the same number of flatten operations; either side is fine.

So after finding the half-sum split, recurse into the shorter side and throw away the longer side. Brutal, but correct.

Algorithm

For each test case:

1. Query the sum of the whole array, call it $S$.
2. Let the current interval be $[1,n]$.
3. While the current interval has length more than $1$:
   • set $H=S/2$;
   • binary search for the unique cut $m$ with sum $[l,m] = H$;
   • compare the lengths of $[l,m]$ and $[m+1,r]$;
   • keep the shorter interval;
   • set $S=H$.
4. When one position remains, its value is exactly the current interval sum $S$, so output $S$.

Query count

Each recursion keeps an interval of length at most half the previous one. A binary search on length $L$ costs $O(\log L)$ queries.

So the total is roughly

$$\log n + \log(n/2) + \log(n/4) + \cdots,$$

which is under $200$ for $n \le 10^5$, plus the initial total-sum query. The limit is $300$, so we are comfortably inside it.