seuOJ477 - 递增的数组

• 题目类型：交互
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：Div.1, 2024

题目描述

这是一道交互题。

有一个长度为 $n$ 的数组 $a$，和一个初始为空的数组 $b$。你和你的朋友在这两个数组上玩一个游戏。你和你的朋友轮流进行操作，且由你先手。在每次操作中，你或者你的朋友从数组 $a$ 的最左端或者最右端取出一个数字，在数字被取出后，数组 $a$ 的长度会减少 $1$。从 $a$ 中取出的数字会被放入数组 $b$ 的尾部，但是放入的前提是在放入新的数字后，数组 $b$ 是严格递增的。最终，你和你的朋友中无法再做出取数字的人输掉游戏。

现在，请你给出一个取数字的方法，使得你必然可以赢得游戏，或者表明，在你的朋友每次取数字都做出最优解的情况下，你不可能赢得游戏的胜利。

输入格式

第一行，一个整数 $t(1\le t \le 10^4)$，代表测试数据的组数。

对于每组数据：
第一行，一个整数 $n(1\le n \le 3·10^5)$，代表数据组数。
接下来的一行共有 $n$ 个整数 $a_i(0\le a_i\le 10^9)$，代表序列 $a$，序列 $b$ 在初始时是空的。

保证在同一测试点内的 $\sum n\le 3·10^5$。

输出格式

对于每组数据，如果你存在某种操作顺序，使得你必然可以赢得游戏，你会和交互器交互 $k(1\le k \le \lceil\frac{n}{2}\rceil)$ 次。
对于每次交互：
首先，你输出一个整数 $pos(1\le pos \le n)$，代表你取出的数字的下标，请注意，你必须取出当前数组 $a$ 最左端或者最右端的数字，且在该数字放入数组 $b$ 中后，数组 $b$ 严格单调递增。
在你每次输出一个整数后，交互器会输出一个数字 $pos(1\le pos \le n)$，代表你的朋友取出的数字的下标，保证你朋友取出的数字是符合题目要求的。
假如说，你的朋友已经无法取出数字，即你已经胜利，那么交互器会返回 $0$。

否则，你只会和交互器交互 $1$ 次。
如果你认为，在你的朋友每次取数字都做出最优操作的情况下，你不可能赢得游戏的胜利，请直接输出一个 $0$ 。
如果你的判断正确，交互器会返回一个数字 $0$。

假如你的判断不正确或者给出的操作不合法，交互器会返回 $-1$。如果收到错误答案的判断，程序应立即终止。否则，你的代码可能会得到 $\texttt{Wrong Answer}$ 以外的结果。

在每次输出后，不要忘记刷新缓冲区，不然，你会得到 $\texttt{Idleness limit exceeded}$ 或者 $\texttt{Time limit exceeded}$，为了避免这一点，请使用：

• C++ 中的 $\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$；
• Java 中的 $\texttt{System.out.flush()}$；
• Pascal 中的 $\texttt{flush(output)}$；
• Python 中的 $\texttt{stdout.flush()}$；
• 其他语言请参见文档。

样例

输入样例

3
2
114 514

0

5
1 2 3 4 5

2

4

0

6
1 2 7 4 5 3

2

0

输出样例

2

1

3

5

1

3

提示
请注意，样例并不一定是最佳策略或正确的选择。

在第 $1$ 组数据中，你直接取出了数组 $a$ 中第 $2$ 个数字，你的朋友无法再取出数字，所以交互器输出了一个 $0$，代表你的判断正确且最终获得了游戏胜利。