310925: CF1910D. Remove and Add

D. Remove and Addtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ integers.

You goal is to make is strictly increasing. To achieve that, you perform each of the following operations exactly once:

• first, remove any element;
• second, select any number of elements (possibly, none or all $n-1$) and add $1$ to them.

Note that you are not allowed to rearrange the elements of the array.

For the resulting array $a'$, $a'_1 < a'_2 < \dots < a'_{n-1}$ should hold. Determine if it's possible to achieve that.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements of the array.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$).

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

Output

For each testcase, print YES if it's possible to remove one element and add $1$ to some elements (possibly, none or all), so that the array becomes strictly increasing. Otherwise, print NO.

ExampleInput

8
4
4 4 1 5
5
4 4 1 5 5
2
10 5
3
1 2 3
3
2 1 1
4
1 1 1 1
4
1 3 1 2
5
1 1 3 3 1

Output

YES
NO
YES
YES
YES
NO
YES
YES

Note

In the first testcase, you can remove the third element and add $1$ to the second and the last element. $a'$ will become $[4, 5, 6]$, which is strictly increasing.

In the second testcase, there is no way to perform the operations, so that the result is strictly increasing.

In the third testcase, you can remove either of the elements.

In the fourth testcase, you are already given a strictly increasing array, but you still have to remove an element. The result $a'$ can be $[1, 3]$, for example.

题目大意：
给定一个由n个整数组成的数组a1, a2, …, an。目标是使其严格递增。为实现这一目标，执行以下操作恰好一次：首先，删除任意一个元素；其次，选择任意数量的元素（可能为0个或所有n-1个）并将它们加1。注意，不允许重新排列数组的元素。对于结果数组a'，需要满足a'1 < a'2 < … < a'n-1。确定是否可以实现这一目标。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）——数组元素的数量。
第二行包含n个整数a1, a2, …, an（1≤ai≤10^6）。
所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，如果可以通过删除一个元素并对某些元素加1（可能为0个或所有元素），使数组变为严格递增，则打印YES。否则，打印NO。

示例：
输入：
8
4
4 4 1 5
5
4 4 1 5 5
2
10 5
3
1 2 3
3
2 1 1
4
1 1 1 1
4
1 3 1 2
5
1 1 3 3 1

输出：
YES
NO
YES
YES
YES
NO
YES
YES

注意：
在第一个测试用例中，可以删除第三个元素并对第二个和最后一个元素加1。a'将变为[4, 5, 6]，这是严格递增的。
在第二个测试用例中，无法执行操作以使结果严格递增。
在第三个测试用例中，可以删除任一元素。
在第四个测试用例中，已经给出了一个严格递增的数组，但仍然需要删除一个元素。结果a'可以是[1, 3]，例如。题目大意： 给定一个由n个整数组成的数组a1, a2, …, an。目标是使其严格递增。为实现这一目标，执行以下操作恰好一次：首先，删除任意一个元素；其次，选择任意数量的元素（可能为0个或所有n-1个）并将它们加1。注意，不允许重新排列数组的元素。对于结果数组a'，需要满足a'1 < a'2 < … < a'n-1。确定是否可以实现这一目标。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）——数组元素的数量。 第二行包含n个整数a1, a2, …, an（1≤ai≤10^6）。 所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，如果可以通过删除一个元素并对某些元素加1（可能为0个或所有元素），使数组变为严格递增，则打印YES。否则，打印NO。 示例： 输入： 8 4 4 4 1 5 5 4 4 1 5 5 2 10 5 3 1 2 3 3 2 1 1 4 1 1 1 1 4 1 3 1 2 5 1 1 3 3 1 输出： YES NO YES YES YES NO YES YES 注意： 在第一个测试用例中，可以删除第三个元素并对第二个和最后一个元素加1。a'将变为[4, 5, 6]，这是严格递增的。 在第二个测试用例中，无法执行操作以使结果严格递增。 在第三个测试用例中，可以删除任一元素。 在第四个测试用例中，已经给出了一个严格递增的数组，但仍然需要删除一个元素。结果a'可以是[1, 3]，例如。