CF2152E Monotone Subsequence

This is an interactive problem. Faker is being naughty again. You asked him to create a nice query problem, but he created an interactive problem where he is answering a query instead! Faker hid a permutation from you, and you have to infer some interesting information by interacting with him. You are given an integer $ n $ . Faker hid a hidden permutation $ ^{\text{∗}} $ $ p_1, p_2, \ldots, p_{n^2+1} $ of length $ n^2+1 $ . Your goal is to find a monotone subsequence (either increasing or decreasing) of the hidden permutation, with length exactly $ n+1 $ . It can be proved that every permutation of length $ n^2 + 1 $ contains a monotone subsequence of length $ n+1 $ . For more information about the proof, you can check out [this Wikipedia page](https://en.wikipedia.org/wiki/Erdos-Szekeres%20theorem). To find it, you can make at most $ n $ skyscraper queries to the interactor, which is defined as follows: - You provide a set of $ k $ indices as a strictly increasing sequence: $ i_1, i_2, \ldots, i_k $ . - The interactor considers the values of the hidden permutation at these indices: $ p_{i_1}, p_{i_2}, \ldots, p_{i_k} $ . - The interactor then returns the indices corresponding to the visible skyscrapers from this set. An index $ i_j $ is visible if its value $ p_{i_j} $ is greater than the values of all preceding elements in your query, i.e., $ p_{i_j} > p_{i_m} $ for all $ 1 \le m < j $ . This is equivalent to finding the indices of the left-to-right maxima of the sequence $ (p_{i_1}, \ldots, p_{i_k}) $ . After making at most $ n $ queries, you must report a valid monotone subsequence of length exactly $ n+1 $ . Note that the permutation $ p $ is fixed before any queries are made and does not depend on the queries. $ ^{\text{∗}} $ A permutation of length $ m $ is an array consisting of $ m $ distinct integers from $ 1 $ to $ m $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ m=3 $ but there is $ 4 $ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows. The first and only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ). It is guaranteed that the sum of $ n^2+1 $ over all test cases does not exceed $ 10\,001 $ .

N/A

For the first test case, $ n=1 $ . The hidden permutation is $ p=[1, 2] $ . - For the query ? 2 1 2, the visible skyscrapers are at indices $ 1 $ and $ 2 $ . The interactor returns 2 1 2. - An increasing subsequence of length $ 2 $ at indices $ 1, 2 $ is reported. For the second test case, $ n=2 $ . The hidden permutation is $ p=[5, 3, 4, 1, 2] $ . - For the query ? 3 1 2 3, the visible skyscraper is at index $ 1 $ . The interactor returns 1 1. - For the query ? 3 2 3 5, the visible skyscrapers are at indices $ 2 $ and $ 3 $ . The interactor returns 2 2 3. - A decreasing subsequence of length $ 3 $ at indices $ 1, 3, 4 $ is reported. Although Faker will play the role of interactor, the interactor will never lie to you.