[Problem E. Monotone Subsequence](https://mirror.codeforces.com/contest/2152/problem/E)↵
↵
Suppose you made a query $[i_1, i_2, \ldots, i_k]$ and got a response $[j_1, j_2, \ldots, j_c]$. From the definition of visible skyscrapers, you can tell $i_1 = j_1$, and the following holds: $$\begin{align*}↵
p_{j_1} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_1 < i_t < j_2, \\↵
p_{j_2} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_2 < i_t < j_3, \\↵
& \quad \vdots \\↵
p_{j_{c-1}} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_{c-1} < i_t < j_c, \\↵
p_{j_c} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_c < i_t.↵
\end{align*}$$↵
↵
Based on this, think about the following algorithm:↵
↵
* Initially $S_0 = \\{ 1, 2, \ldots, n^2 + 1 \\}$.↵
* Do the following $n$ times. In the $r$-th round $(1 \le r \le n)$, make a query consisting of all indices in $S_{r-1}$. Suppose you get a response $[j_1, j_2, \ldots, j_c]$. If $c \ge n+1$, you take any subsequence of length $n+1$ out of the response and make it an answer (because it's clearly increasing), then quit. Otherwise, $S_r = S_{r-1} \setminus \\{ j_u \; | \; 1 \le u \le c \\}$, then repeat.↵
↵
Let's say you have completed $n$ rounds without making an answer. Clearly $S_0 \supset S_1 \supset \cdots \supset S_n$. Furthermore, $\left| S_{r-1} \right| - \left| S_{r} \right| \le n$, thus $\left| S_n \right| \ge (n^2 + 1) - n \cdot n = 1$.↵
↵
Consider a directed graph $G$ consisting of $n^2 + 1$ vertices, initially with no edges. In round $r$, for every $j \in S_r$, there exists $i \in S_{r-1} \setminus S_{r}$ that satisfies $p_i > p_j$, using the relationship stated above. For every such $(i, j)$, add an edge $(i, j)$ to $G$. Then, for every $j \in S_r$, there is a path of length $r$ in $G$, ending at the vertex $j$ (this can be easily proofed by induction). Therefore, after all rounds are processed, there is a path of length $n$ in $G$, ending at a vertex $j$ for any $j \in S_n$. Take any such path, then the $n + 1$ vertices in that path is an acceptable answer, because it forms an decreasing sequence.↵
↵
**Implementation note**: The following is an easy way to find the final path. First, create an array $b = [-1, -1, \ldots, -1]$ of length $n^2 + 1$. For every round, record back edges: do $b[j] := i$ for every edge $(i, j)$ added to $G$. Then you can backtrack and recover the path, starting from any vertex in $S_n$.
↵
Suppose you made a query $[i_1, i_2, \ldots, i_k]$ and got a response $[j_1, j_2, \ldots, j_c]$. From the definition of visible skyscrapers, you can tell $i_1 = j_1$, and the following holds: $$\begin{align*}↵
p_{j_1} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_1 < i_t < j_2, \\↵
p_{j_2} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_2 < i_t < j_3, \\↵
& \quad \vdots \\↵
p_{j_{c-1}} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_{c-1} < i_t < j_c, \\↵
p_{j_c} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_c < i_t.↵
\end{align*}$$↵
↵
Based on this, think about the following algorithm:↵
↵
* Initially $S_0 = \\{ 1, 2, \ldots, n^2 + 1 \\}$.↵
* Do the following $n$ times. In the $r$-th round $(1 \le r \le n)$, make a query consisting of all indices in $S_{r-1}$. Suppose you get a response $[j_1, j_2, \ldots, j_c]$. If $c \ge n+1$, you take any subsequence of length $n+1$ out of the response and make it an answer (because it's clearly increasing), then quit. Otherwise, $S_r = S_{r-1} \setminus \\{ j_u \; | \; 1 \le u \le c \\}$, then repeat.↵
↵
Let's say you have completed $n$ rounds without making an answer. Clearly $S_0 \supset S_1 \supset \cdots \supset S_n$. Furthermore, $\left| S_{r-1} \right| - \left| S_{r} \right| \le n$, thus $\left| S_n \right| \ge (n^2 + 1) - n \cdot n = 1$.↵
↵
Consider a directed graph $G$ consisting of $n^2 + 1$ vertices, initially with no edges. In round $r$, for every $j \in S_r$, there exists $i \in S_{r-1} \setminus S_{r}$ that satisfies $p_i > p_j$, using the relationship stated above. For every such $(i, j)$, add an edge $(i, j)$ to $G$. Then, for every $j \in S_r$, there is a path of length $r$ in $G$, ending at the vertex $j$ (this can be easily proofed by induction). Therefore, after all rounds are processed, there is a path of length $n$ in $G$, ending at a vertex $j$ for any $j \in S_n$. Take any such path, then the $n + 1$ vertices in that path is an acceptable answer, because it forms a
↵
**Implementation note**: The following is an easy way to find the final path. First, create an array $b = [-1, -1, \ldots, -1]$ of length $n^2 + 1$. For every round, record back edges: do $b[j] := i$ for every edge $(i, j)$ added to $G$. Then you can backtrack and recover the path, starting from any vertex in $S_n$.
