CF2234G.Stripe, Token and Two Players

There is a stripe of $n + 1$ cells, numbered from $1$ to $n + 1$. Initially, there is a token with power $1$ on cell number $1$, and the numbers $a_1, a_2, \ldots, a_n$ are written on cells $1, 2, \ldots, n$ respectively.

Two players play a game. On each move, the player performs the following actions in order:

1. Suppose the token is on cell number $i$.
2. The player may increase the power of the token by any integer from $0$ to $a_i$ inclusive.
3. Then the player moves the token forward by any positive integer not exceeding the token's power, such that after this action the token does not leave the stripe.

The player after whose move the token lands on cell $n + 1$ wins.

Who wins with optimal play?

有一条包含 $n + 1$ 个格子的带状区域，编号从 $1$ 到 $n + 1$。初始时，一个力量值为 $1$ 的棋子位于第 $1$ 号格子上，且格子 $1, 2, \ldots, n$ 上分别写有数字 $a_1, a_2, \ldots, a_n$。

两名玩家进行一场游戏。在每一步中，当前玩家按以下顺序执行如下操作：

1. 假设棋子当前位于第 $i$ 号格子；
2. 玩家可将棋子的力量值增加任意一个介于 $0$ 到 $a_i$（含端点）之间的整数；
3. 然后，玩家将棋子向前移动任意一个正整数步数，该步数不超过棋子当前的力量值，且移动后棋子不能离开该带状区域（即不能超出第 $n+1$ 号格子）。

在某位玩家完成移动后，若棋子恰好落在第 $n + 1$ 号格子上，则该玩家获胜。

在双方均采取最优策略的情况下，谁将获胜？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the number of written numbers.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the numbers written on the cells.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output one integer, $1$ or $2$ — the number of the player who wins with optimal play. (Player $1$ makes the first move.)

对于每个测试用例，输出一个整数 $1$ 或 $2$ —— 表示在双方均采取最优策略时获胜的玩家编号。（玩家 $1$ 先手。）

In the first test case, the power of the token remains equal to $1$ throughout the game, so on every move the players must move exactly one cell forward. Thus, $3$ moves will be made, and the last move will be made by player $1$, so he will win in any case.

In the second test case, player $2$ has a winning strategy: on their very first move, increase the token's power as much as possible, and then jump to cell $4$ and win. This is always possible, since at the start of the move the token will be on cell $2$ or $3$, and its power can be increased to at least $2$.

在第一个测试用例中，令牌的权值在整个游戏中始终保持为 $1$，因此每一步玩家都必须恰好向前移动一格。于是总共将进行 $3$ 步，且最后一步由玩家 $1$ 执行，因此他必胜。

在第二个测试用例中，玩家 $2$ 存在必胜策略：在其第一步中，尽可能增大令牌的权值，然后跳至第 $4$ 格并获胜。这总是可行的，因为该步开始时令牌位于第 $2$ 或第 $3$ 格，其权值可至少提升至 $2$。