← 返回题目列表

Codeforces · 1291/B

B. 阵列锐化

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

给定一个数组 $$$a_1, \ldots, a_n$$$,其中包含 $$$n$$$ 非负整数。

当且仅当存在一个整数 $$$1 \le k \le n$$$ 使得 $$$a_1 < a_2 < \ldots < a_k$$$ 且 $$$a_k > a_{k+1} > \ldots > a_n$$$ 时,我们称其为锐化。特别是,任何严格递增或严格递减的数组都会被锐化。例如:

- 数组 $$$[4]$$$、$$$[0, 1]$$$、$$$[12, 10, 8]$$$ 和 $$$[3, 11, 15, 9, 7, 4]$$$ 被锐化;
- 数组 $$$[2, 8, 2, 8, 6, 5]$$$、$$$[0, 1, 1, 0]$$$ 和 $$$[2, 5, 6, 9, 8, 8]$$$ 未锐化。

您可以根据需要多次执行以下操作:选择数组中任何严格为正的元素,并将其减一。形式上,您可以选择任何 $$$i$$$ ($$$1 \le i \le n$$$) 使得 $$$a_i>0$$$ 并分配 $$$a_i := a_i - 1$$$。

判断是否可以使用这些操作中的一些(可能为零)来锐化给定的数组。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 15\ 000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。

每个测试用例的第二行包含一系列 $$$n$$$ 非负整数 $$$a_1, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

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

输出

对于每个测试用例,如果可以使用所描述的操作使给定数组锐化,则输出包含“是”(不带引号)的单行,否则输出“否”(不带引号)。

示例

输入 #1

10
1
248618
3
12 10 8
6
100 11 15 9 7 8
4
0 1 1 0
2
0 0
2
0 1
2
1 0
2
1 1
3
0 1 0
3
1 0 1

输出 #1

Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No

注意

在第一个测试的第一个和第二个测试用例中,给定的数组已经被锐化。

在第一个测试的第三个测试用例中,我们可以将数组转换为$$$[3, 11, 15, 9, 7, 4]$$$(将第一个元素减少$$$97$$$倍,将最后一个元素减少$$$4$$$倍)。它被锐化是因为 $$$3 < 11 < 15$$$ 和 $$$15 > 9 > 7 > 4$$$。

在第一个测试的第四个测试用例中,不可能使给定的数组锐化。