← 返回题目列表

Codeforces · 1910/D

D. 删除并添加

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

给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 整数组成。

你的目标是严格增加。为此,您只需执行一次以下每个操作:

- 首先,删除任何元素;
- 其次,选择任意数量的元素(可能没有或全部 $$$n-1$$$)并向其中添加 $$$1$$$。

请注意,不允许重新排列数组的元素。

对于结果数组 $$$a'$$$,$$$a'_1 < a'_2 < \dots < a'_{n-1}$$$ 应该成立。确定是否有可能实现这一目标。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组元素的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。

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

输出

对于每个测试用例,如果可以删除一个元素并将 $$$1$$$ 添加到某些元素(可能没有或全部),则打印 YES,以便数组严格递增。否则,打印NO。

示例

输入 #1

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

输出 #1

YES
NO
YES
YES
YES
NO
YES
YES

注意

在第一个测试用例中,您可以删除第三个元素并将 $$$1$$$ 添加到第二个也是最后一个元素。 $$$a'$$$ 将变为 $$$[4, 5, 6]$$$,严格递增。

在第二个测试用例中,无法执行操作,因此结果是严格递增的。

在第三个测试用例中,您可以删除任一元素。

在第四个测试用例中,您已经给出了一个严格递增的数组,但您仍然需要删除一个元素。例如,结果 $$$a'$$$ 可以是 $$$[1, 3]$$$。