给你一个序列 $$$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”否则。
任何情况下都可以输出答案。例如,字符串“是", "是的“,和”是”也将被视为积极响应。
示例
输入复制
6324 0 030 15 0415 14 5 640 1 0 088 7 6 5 4 3 2 164 1 5 4 1 1
输出复制
NoYesNoYesNoYes
注意
对于第一个测试用例,不可能使 $$$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}}}]$$$。