← 返回题目列表

Codeforces · 2211/G

G. 理性冒泡排序

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

给你一个序列 $$$a_1,a_2,\ldots,a_n$$$ 组成 理性 值。最初,每个 $$$a_i$$$ 都是从 $$$0$$$ 到 $$$10^6$$$ 的整数(包括 $$$0$$$)。

您可以执行以下操作任意次数(可能为零):

  • 选择索引 $$$i$$$,使得 $$$1 \le i \lt n$$$,并让 $$$z=\frac{{1}}{{2}}(a_{i}+a_{i+1})$$$。
  • 然后,将 $$$a_i$$$ 和 $$$a_{i+1}$$$ 都设置为 $$$z$$$ 的值。

例如,令 $$$a=[0,15,0]$$$。如果对 $$$i=2$$$ 执行操作,则 $$$a$$$ 变为 $$$[0,\color{red}{7.5},\color{red}{7.5}]$$$。

请确定是否可以将 $$$a$$$ 排序 非递减 订单。

输入

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

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

每个测试用例的第二行包含 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 10^6$$$)。

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

输出

对于每个测试用例,输出“是"如果可以使 $$$a$$$ 排序 非递减 订单,或“No”否则。

任何情况下都可以输出答案。例如,字符串“是", "是的“,和”是”也将被视为积极响应。

示例

输入
复制

6
3
24 0 0
3
0 15 0
4
15 14 5 6
4
0 1 0 0
8
8 7 6 5 4 3 2 1
6
4 1 5 4 1 1

输出
复制

No
Yes
No
Yes
No
Yes

注意

对于第一个测试用例,不可能使 $$$a$$$ 按非降序排序。

第二个测试用例在声明中进行了解释。

对于第四个测试用例,$$$a$$$ 可以按非降序排序为 $$$[0,1,0,0] \to [0,\color{red}{\frac{{1}}{{2}}},\color{red}{\frac{{1}}{{2}}},0] \to [\color{red}{\frac{{1}}{{4}}}、\color{red}{\frac{{1}}{{4}}}、\frac{{1}}{{2}},0] \至 [\frac{{1}}{{4}}、\frac{{1}}{{4}}、\color{red}{\frac{{1}}{{4}}}、\color{red}{\frac{{1}}{{4}}}]$$$。