CF2155C.The Ancient Wizards' Capes

There are $n$ wizards in a row numbered $1$ to $n$ from left to right. Each wizard has an invisibility cape which can be worn either on his left side or on his right side. Harry walks from the position of wizard $1$ until the position of wizard $n$ ($1 \le n \le 10^5$), and registers how many wizards he sees from each wizard's position. A wizard in position $j$ is visible from position $i$ if:

• Wizard $j$ wears his cape on his left side and $i \ge j$.
• Wizard $j$ wears his cape on his right side and $i \le j$.

In particular, note that wizard $i$ is visible from position $i$.

Harry's list is very old but, after much work, you managed to decipher it. The list is an array $a$ of $n$ elements, where the $i$-th element $a_i$ ($1 \le a_i \le n$) is the number of wizards that Harry saw from the position of wizard $i$.

Your task is to determine how many of all the possible cape arrangements that Harry could have seen are consistent with the data recorded by the list, modulo $676\,767\,677$.

有 $n$ 个巫师从左到右排成一列，编号为 $1$ 到 $n$。每位巫师拥有一件隐形斗篷，可披在左侧或右侧。哈利从巫师 $1$ 的位置出发，一直走到巫师 $n$ 的位置（$1 \le n \le 10^5$），并记录下从每位巫师位置所能看到的巫师数量。位置为 $j$ 的巫师在位置 $i$ 处可见，当且仅当满足以下任一条件：

• 巫师 $j$ 将斗篷披在左侧，且 $i \ge j$；
• 巫师 $j$ 将斗篷披在右侧，且 $i \le j$。

特别地，请注意：巫师 $i$ 在其自身位置 $i$ 处总是可见的。

哈利的记录清单年代久远，但经过大量努力，你已成功将其破译。该清单是一个长度为 $n$ 的数组 $a$，其中第 $i$ 个元素 $a_i$（$1 \le a_i \le n$）表示哈利从巫师 $i$ 的位置所看到的巫师总数。

你的任务是：计算所有可能的斗篷穿戴方式中，有多少种与清单 $a$ 所记录的数据一致，结果对 $676\,767\,677$ 取模。

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 a single integer $n$ ($1 \le n \le 10^5$) — the length of $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$.

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$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）—— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, print one integer — the number of arrangements for the wizards' capes that satisfy the condition, modulo $676\,767\,677$.

对于每个测试用例，输出一个整数——满足条件的巫师斗篷排列方案数，对 $676\,767\,677$ 取模。

The image below shows an arrangement of capes that matches Harry's list in the second test case.

Wizard 1 has the invisibility cape on his left side, while wizards $2$, $3$, and $4$ wear it on their right side.

• From position $1$, we can see wizards $1$, $2$, $3$, and $4$.
• From position $2$, we can see wizards $1$, $2$, $3$, and $4$.
• From position $3$, we can see wizards $1$, $3$, and $4$.
• From position $4$, we can see wizards $1$ and $4$.

Thus, Harry's list ends up being $[4, 4, 3, 2]$. It can be proved that this is the only possible arrangement.

In the third test case, it can be proved that Harry could not have obtained his list from any cape arrangement.

In the fifth case, note that there are two possible cape arrangements from which Harry could have gotten his list:

• $1 \mid \quad \mid 2 \quad 3 \, \mid$
• $\mid \, 1 \quad 2 \mid \quad \mid 3$

下图展示了一种斗篷排列方式，该方式与第二个测试用例中哈利的列表相匹配。

巫师 1 将隐形斗篷戴在左侧，而巫师 $2$、$3$ 和 $4$ 则将其戴在右侧。

• 从位置 $1$ 出发，我们可以看到巫师 $1$、$2$、$3$ 和 $4$；
• 从位置 $2$ 出发，我们可以看到巫师 $1$、$2$、$3$ 和 $4$；
• 从位置 $3$ 出发，我们可以看到巫师 $1$、$3$ 和 $4$；
• 从位置 $4$ 出发，我们可以看到巫师 $1$ 和 $4$。

因此，哈利的列表最终为 $[4, 4, 3, 2]$。可以证明，这是唯一可能的排列方式。

在第三个测试用例中，可以证明：不存在任何斗篷排列方式，能使哈利得到他所记录的列表。

在第五个测试用例中，请注意存在两种可能的斗篷排列方式，均能产生哈利所记录的列表：

• $1 \mid \quad \mid 2 \quad 3 \, \mid$
• $\mid \, 1 \quad 2 \mid \quad \mid 3$