← 返回题目列表

Codeforces · 1851/D

D. 前缀排列和

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

你的朋友有一个 $$$n$$$ 元素数组,计算了它的前缀和数组并将其传递给你,在传输过程中意外丢失了一个元素。你的任务是找出给定的数组是否可以匹配排列。

$$$n$$$ 元素的排列是从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 数字数组,使得每个数字在其中恰好出现一次。

数组 $$$a$$$ 的前缀和数组 — 是这样一个数组 $$$b$$$,$$$b_i = \sum_{j=1}^i a_j, 1 \le i \le n$$$。

例如,原始排列为 $$$[1, 5, 2, 4, 3]$$$。它的前缀和数组 — $$$[1, 6, 8, 12, 15]$$$。例如,丢失一个元素后,您可以获得数组 $$$[6, 8, 12, 15]$$$ 或 $$$[1, 6, 8, 15]$$$。

还可以证明数组$$$[1, 2, 100]$$$不对应于任何排列。

输入

第一行包含一个正数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例描述的第一行包含一个正数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 初始数组的大小。

每个测试用例描述的第二行包含 $$$n - 1$$$ 正数 $$$a_i$$$ ($$$1 \le a_i \le 10^{18}$$$), $$$a_{i-1} < a_i$$$ — 前缀和数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果存在这种排列,则输出“YES”,否则输出“NO”。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

12
5
6 8 12 15
5
1 6 8 15
4
1 2 100
4
1 3 6
2
2
3
1 2
4
3 7 10
5
5 44 46 50
4
1 9 10
5
13 21 36 42
5
1 2 3 1000000000000000000
9
9 11 12 20 25 28 30 33

输出 #1

YES
YES
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO

注意

例如,在第四个示例中,排列$$$[1,2,3,4]$$$是合适的。例如,在第五示例中,排列$$$[2, 1]$$$是合适的。例如,在第七个示例中,排列$$$[1,2,4,3]$$$是合适的。