CF2234G Stripe, Token and Two Players

有一条由 $n+1$ 个格子组成的带，编号从 $1$ 到 $n+1$。一开始，第 $1$ 个格子上有一个权值为 $1$ 的棋子，第 $1 \sim n$ 个格子上分别写有数 $a_1, a_2, \ldots, a_n$。 有两名玩家进行游戏，每次轮到玩家操作时，按以下顺序进行： 1. 设当前棋子在第 $i$ 个格子。 2. 玩家可以将棋子的权值增加任意整数，范围是 $0$ 到 $a_i$ 之间（包含 $0$ 和 $a_i$）。 3. 然后，玩家可以将棋子向前移动任意正整数步，但不能超过当前棋子的权值，且移动后不能超出这条带的末端。 使棋子恰好落在第 $n+1$ 个格子的那一步的玩家获胜。 两人都采取最优策略时，谁能获胜？

每个测试点包含多组测试用例。第一行为测试用例组数 $t$（$1 \le t \le 10^4$）。 每组测试用例第一行一个整数 $n$（$1 \le n \le 10^5$），表示带上写有数字的格子数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示每个格子上写的数字。 保证所有测试用例中 $n$ 之和不超过 $10^5$。

对于每组测试用例，输出一个整数 $1$ 或 $2$，表示在双方都采取最优策略的情况下，第几位玩家获胜（玩家 $1$ 先手）。

在第一个测试用例中，棋子的权值始终为 $1$，因此每次只能前进一步。总共需要移动 $3$ 步，最后一步由玩家 $1$ 完成，所以他一定会获胜。 在第二个测试用例中，玩家 $2$ 有必胜策略：在他第一次操作时，将棋子的权值升到最大，然后直接跳到第 $4$ 个格子获胜。这总是可行的，因为无论轮到他行动时棋子在第 $2$ 还是第 $3$ 个格子，其权值都可以升至少为 $2$。 由 ChatGPT 5 翻译