← 返回题目列表

Codeforces · 2128/C

C. 下面最左边

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

考虑一个数组 $$$a_1, \ldots, a_n$$$。最初,对于每个 $$$i$$$,$$$a_i = 0$$$。

您可以执行以下形式的操作。

  • 您选择一个大于 $$$\min(a)$$$ 的整数 $$$x$$$。
  • 然后,$$$i$$$ 被定义为满足 $$$a_i \lt x$$$ 的最小索引。换句话说,$$$i$$$ 是 $$$1$$$ 和 $$$n$$$ 之间的唯一整数,使得每个 $$$1 \leq j \leq i-1$$$ 都满足 $$$a_i \lt x$$$ 和 $$$a_j \geq x$$$。
  • 最后,$$$a_i$$$ 增加$$$x$$$。

例如,如果 $$$a = [6, 8, 2, 1]$$$ 并且您选择 $$$x = 6$$$,则 $$$i$$$ 将等于 $$$3$$$(因为 $$$a_1 \geq 6$$$、$$$a_2 \geq 6$$$ 和 $$$a_3 \lt 6$$$)并且$$$a$$$ 将变为 $$$[6, 8, 8, 1]$$$。

您可以执行任意数量的操作。你能到达目标数组 $$$b_1, \ldots, b_n$$$ 吗?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 200\,000$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,打印 是 如果你能到达目标阵列并且 NO 否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

4
4
5 6 1 1
3
3 1 2
3
40 60 90
2
1 1

输出
复制

YES
NO
NO
YES

注意

在第一个测试用例中,我们可以执行以下操作序列:

  • 我们选择$$$x=2$$$,$$$a$$$ 变为$$$[2, 0, 0, 0]$$$
  • 我们选择$$$x=2$$$,$$$a$$$ 变为$$$[2, 2, 0, 0]$$$
  • 我们选择$$$x=3$$$,$$$a$$$ 变为$$$[5, 2, 0, 0]$$$
  • 我们选择$$$x=4$$$,$$$a$$$ 变为$$$[5, 6, 0, 0]$$$
  • 我们选择$$$x=1$$$,$$$a$$$ 变为$$$[5, 6, 1, 0]$$$
  • 我们选择$$$x=1$$$,$$$a$$$ 变为$$$[5, 6, 1, 1]$$$

在第二个测试用例中,我们可以证明没有办法达到$$$[3, 1, 2]$$$。