← 返回题目列表

Codeforces · 1910/G

G. 池记录

中文机器翻译题面 查看原题

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$$$。