← 返回题目列表

Codeforces · 1713/B

B. 最佳减少

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

考虑一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。

您可以执行以下操作:

- 选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$),然后
- 将所有元素 $$$a_l, a_{l + 1}, \dots, a_r$$$ 减少 $$$1$$$。

我们将 $$$f(a)$$$ 称为将数组 $$$a$$$ 更改为 $$$n$$$ 零数组所需的最少操作数。

确定对于 $$$a$$$ 的所有排列$$$^\dagger$$$ $$$b$$$,$$$f(a) \leq f(b)$$$ 是否为真。

$$$^\dagger$$$ 数组 $$$b$$$ 是数组 $$$a$$$ 的排列,如果 $$$b$$$ 由 $$$a$$$ 的元素以任意顺序组成。例如,$$$[4,2,3,4]$$$ 是 $$$[3,2,4,4]$$$ 的排列,而 $$$[1,2,2]$$$ 不是 $$$[1,2,3]$$$ 的排列。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的描述。

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

输出

对于每个测试用例,如果对于 $$$a$$$ 的所有排列 $$$b$$$,$$$f(a) \leq f(b)$$$ 为真,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

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

示例

输入 #1

3
4
2 3 5 4
3
1 2 3
4
3 1 3 2

输出 #1

YES
YES
NO

注意

在第一个测试用例中,我们可以在$$$5$$$操作中将所有元素更改为$$$0$$$。可以证明$$$[2,3,5,4]$$$的排列不需要少于$$$5$$$操作来将所有元素更改为$$$0$$$。

在第三个测试用例中,我们需要 $$$5$$$ 操作将所有元素更改为 $$$0$$$,而 $$$[2, 3, 3, 1]$$$ 只需要 $$$3$$$ 操作。