310558: CF1851D. Prefix Permutation Sums

D. Prefix Permutation Sumstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Your friends have an array of $n$ elements, calculated its array of prefix sums and passed it to you, accidentally losing one element during the transfer. Your task is to find out if the given array can matches permutation.

A permutation of $n$ elements is an array of $n$ numbers from $1$ to $n$ such that each number occurs exactly one times in it.

The array of prefix sums of the array $a$ — is such an array $b$ that $b_i = \sum_{j=1}^i a_j, 1 \le i \le n$.

For example, the original permutation was $[1, 5, 2, 4, 3]$. Its array of prefix sums — $[1, 6, 8, 12, 15]$. Having lost one element, you can get, for example, arrays $[6, 8, 12, 15]$ or $[1, 6, 8, 15]$.

It can also be shown that the array $[1, 2, 100]$ does not correspond to any permutation.

Input

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

The first line of the description of each test case contains a positive number $n$ ($2 \le n \le 2 \cdot 10^5$) — the size of the initial array.

The second line of the description of each test case contains $n - 1$ positive number $a_i$ ($1 \le a_i \le 10^{18}$), $a_{i-1} < a_i$ — elements of the array of prefix sums.

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

Output

For each test case, output "YES" if such a permutation exists, and "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive response).

ExampleInput

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

Output

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

Note

In the fourth example, for example, the permutation $[1, 2, 3, 4]$ is suitable. In the fifth example, for example, the permutation $[2, 1]$ is suitable. In the seventh example, for example, the permutation $[1, 2, 4, 3]$ is suitable.

题目大意：你的朋友们有一个长度为 \( n \) 的数组，计算了它的前缀和数组，在传递给你时不小心丢失了一个元素。你的任务是判断给定的数组是否可以对应一个排列。

一个长度为 \( n \) 的排列是一个由 \( 1 \) 到 \( n \) 的 \( n \) 个数字组成的数组，每个数字恰好出现一次。

数组 \( a \) 的前缀和数组 \( b \) 是这样一个数组：对于 \( 1 \le i \le n \)，有 \( b_i = \sum_{j=1}^i a_j \)。

例如，原始排列是 \( [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" 都将被识别为肯定响应）。题目大意：你的朋友们有一个长度为 \( n \) 的数组，计算了它的前缀和数组，在传递给你时不小心丢失了一个元素。你的任务是判断给定的数组是否可以对应一个排列。 一个长度为 \( n \) 的排列是一个由 \( 1 \) 到 \( n \) 的 \( n \) 个数字组成的数组，每个数字恰好出现一次。 数组 \( a \) 的前缀和数组 \( b \) 是这样一个数组：对于 \( 1 \le i \le n \)，有 \( b_i = \sum_{j=1}^i a_j \)。 例如，原始排列是 \( [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" 都将被识别为肯定响应）。