Monotone Subsequence

First, Kill the Wrong Assumption

This is interactive. The hidden permutation is not something your solution reads. In hacks, the permutation is given to the interactor, not to your program. Your program only gets query answers. So the job is not “compute LIS from the array”; the job is “force the interactor to reveal enough structure.”

Luckily, the query is absurdly useful: it returns left-to-right maxima.

If you query indices $i_1<i_2<\cdots<i_k$, the answer contains exactly those positions whose values beat every earlier queried value. Therefore the returned indices, in returned order, have strictly increasing values. So every query directly gives an increasing subsequence.

That is half the problem. The other half is what to do when every query is too short.

Peeling Layers

Maintain a sorted list alive of indices that have not been removed yet.

Initially, alive = [1,2,\ldots,n^2+1].

For rounds $r=0,1,\ldots,n-1$:

1. Query all indices currently in alive.
2. Let the answer be $L_r$, the visible skyscrapers among alive.
3. If $|L_r|\ge n+1$, answer with any first $n+1$ indices of $L_r$. They form an increasing subsequence. Done.
4. Otherwise, assign all indices in $L_r$ to layer $r$, and remove them from alive.

This uses at most $n$ queries.

If we never stopped, then every queried visible layer had size at most $n$. Across $n$ rounds, we removed at most

$n\cdot n=n^2$

indices. But the permutation has $n^2+1$ indices, so at least one index remains alive. Assign every still-alive index layer $n$.

Now we have layer labels $0,1,\ldots,n$ available, and we need to turn them into a decreasing subsequence.

Why Layers Create a Decreasing Chain

Here is the key fact:

Suppose index $x$ survives round $r$, meaning it is still alive while we query layer $r$, but it is not returned as visible in that query. Then there is some earlier alive index $y<x$ with $p_y>p_x$.

Why? Because if $x$ is not visible, some previous queried value is larger. Among all visible maxima before $x$, take the last one. That index is returned in the query, so it belongs to layer $r$, and its value is larger than $p_x$.

Now apply this to an index in layer $r+1$. It survived round $r$, but was not removed during round $r$, so the fact above says there is an earlier layer-$r$ index with a larger value.

Even better: the rightmost earlier layer-$r$ index works. The last visible maximum before $x$ in round $r$ is exactly the rightmost layer-$r$ index before $x$; if another layer-$r$ index were between them, it would also be visible and would be later. So we can reconstruct using only indices and layer numbers, no hidden values needed. Pretty slick, honestly.

Building the Decreasing Answer

Scan indices from right to left.

Start looking for layer $n$. Pick the first one you see.

Then keep scanning left looking for layer $n-1$, then $n-2$, and so on down to $0$.

This gives indices in decreasing index order, so reverse them before printing. After reversing, the indices are increasing. By the layer argument, the values strictly decrease from left to right, so this is a valid decreasing subsequence of length $n+1$.

Correctness Proof

We prove the algorithm always outputs a valid monotone subsequence of length exactly $n+1$.

First, if some query returns at least $n+1$ visible indices, those returned indices have strictly increasing values by definition of left-to-right maxima. Taking the first $n+1$ gives an increasing subsequence of length exactly $n+1$.

Otherwise, every one of the $n$ queries returns at most $n$ indices. Thus the total number of removed indices is at most $n^2$. Since there are $n^2+1$ total indices, at least one index remains after all $n$ rounds, so layer $n$ is nonempty.

Now consider any chosen index $x$ of layer $r+1$. During round $r$, $x$ was alive but was not visible; otherwise it would have been removed into layer $r$. Therefore some earlier alive index had value greater than $p_x$. The last visible maximum before $x$ in that round is a layer-$r$ index, lies before $x$, and has value greater than $p_x$. This is exactly the rightmost earlier layer-$r$ index.

So when we scan right-to-left and choose layers $n,n-1,\ldots,0$, every newly chosen index is earlier and has a larger value than the previous chosen index. After reversing the chosen list, indices increase and values strictly decrease. Therefore the output is a decreasing subsequence of length $n+1$.

In all cases, the algorithm outputs a valid monotone subsequence of length exactly $n+1$.

Complexity

The solution makes at most $n$ queries. Locally, it stores and filters $O(n^2)$ indices per test case, so the local work is $O(n^3)$ in the loose bound, easily fine for $n\le 100$. Memory is $O(n^2)$.

Remember to flush after every query and final answer. endl is acceptable here because it flushes; this is one of the few times endl is not just performance cosplay.