Alice 和 Bob 在教练 Monocarp 的指导下在游泳池里游泳。
池可以表示为 OX 轴上从 $$$0$$$ 到 $$$50$$$ 的一段。 Alice 和 Bob 都从 $$$0$$$ 时刻 $$$0$$$ 开始,相应地具有正的实际速度 $$$v_A$$$ 和 $$$v_B$$$。
Alice 和 Bob 都从 $$$0$$$ 游到 $$$50$$$,然后立即转身从 $$$50$$$ 游到 $$$0$$$。在$$$0$$$处,他们再次返回并游至$$$50$$$,依此类推。
Monocarp 记录了有关 Alice 和 Bob 的所有有价值的信息,包括他们在同一点相遇的时刻(Alice 和 Bob 在平行泳道上游泳,因此他们不会互相打扰)。我们将这些时刻命名为序列 $$$t_1, t_2, \dots, t_n$$$。
由于一些事件,Monocarp 几乎丢失了他记录的所有数据,他现在拥有的只有数组$$$t$$$。 Monocarp 记得 Alice 和 Bob 有不同的正真实游泳速度 $$$v_A$$$ 和 $$$v_B$$$ ($$$v_A > 0$$$; $$$v_B > 0$$$; $$$v_A \neq v_B$$$) 并且该序列 $$$t$$$ 包含第一个 $$$n$$$ 相遇时刻。
但是查看序列 $$$t$$$ 他注意到所有 $$$t_i$$$ 都是整数值,现在他怀疑序列 $$$t$$$ 是否有效或者其中存在一些错误。帮助 Monocarp 检查数组 $$$t$$$!
输入
第一行包含一个整数 $$$c$$$ ($$$1 \le c \le 10^4$$$) — 测试用例的数量。然后是 $$$c$$$ 案例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$t$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_1 < \dots < t_n \le 10^9$$$) - 按升序排列的会议时刻。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果数组 $$$t$$$ 是有效数组,或者(换句话说)存在这样的实值 $$$v_A$$$ 和 $$$v_B$$$ ($$$v_A, v_B > 0$$$; $$$v_A \neq v_B$$$) 且数组 $$$t$$$ 包含第一个 $$$n$$$,则打印 VALID爱丽丝和鲍勃在泳池里相遇的时刻。
否则,打印 INVALID。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“vALid”、“valid”、“Valid”和“VALID”将被识别为肯定响应。
示例
输入 #1
7 1 42 4 3 4 6 8 5 1 2 3 4 5 3 999999998 999999999 1000000000 5 4 6 8 12 16 4 6 11 12 14 2 10 30
输出 #1
VALID VALID VALID INVALID VALID INVALID INVALID
注意
在第一个测试用例中,想象一种情况:$$$v_A = 1$$$ 和 $$$v_B = \frac{29}{21}$$$。然后,在 $$$42$$$ 时刻,Alice 和 Bob 将位于 $$$42$$$ 点。
在第二个测试用例中,想象一种情况:$$$v_A = \frac{175}{6}$$$ 和 $$$v_B = \frac{25}{6}$$$。然后,在 $$$3$$$ 时刻,Alice 和 Bob 将在 $$$12.5$$$ 点相遇,在 $$$4$$$ 处,他们将在 $$$\frac{50}{3}$$$ 点相遇,在 $$$6$$$ 时刻,他们将在 $$$25$$$ 处相遇,在 $$$8$$$ 时刻,在 $$$\frac{100}{3}$$$ 点相遇。因为这正是第一次 $$$4$$$ 会议时刻。数组 $$$t$$$ 可能有效。
在第三个测试用例中,可能的情况之一是 $$$v_A = 25$$$ 和 $$$v_B = 75$$$。