← 返回题目列表

Codeforces · 2226/D

D. 保留逆转

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

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。

对于数组中从位置 $$$l$$$ 开始到位置 $$$r$$$ 结束的任何段 ($$$1 \le l \le r \le n$$$),令 $$$m(l, r)$$$ 表示该段中的最小值,$$$M(l, r)$$$ 表示该段中的最大值。正式地,

$$\begin{对齐} m(l,r) &= \min(a_l, a_{l+1}, \ldots, a_r),\\ M(l,r) &= \max(a_l, a_{l+1}, \ldots, a_r).\\ \end{对齐}$$

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

  • 选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 使得 $$$m(l, r) + M(l, r)$$$ 为 奇数;
  • 反转整个段 $$$a_l, a_{l+1}, \ldots, a_r$$$。换句话说,对于每个 $$$i$$$ 和 $$$l \le i \le r$$$,同时设置 $$$a_i := a_{l+r-i}$$$。

判断是否可以将数组$$$a$$$ 非递减$$$^{\text{*}}$$$ 通过执行一系列操作。

$$$^{\text{*}}$$$数组 $$$[b_1, b_2, \ldots, b_k]$$$ 被视为非递减当且仅当 $$$b_1 \le b_2 \le \ldots \le b_k$$$。

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组的元素。

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

输出

对于每个测试用例,打印“是" 如果你可以使数组 $$$a$$$ 非递减,并且 "NO”否则。

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

示例

输入
复制

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

输出
复制

YES
YES
NO
YES
NO
NO

注意

对于第一个测试用例,数组已经是非递减的。因此,输出 YES。

对于第二个测试用例,让我们选择 $$$l = 1$$$ 和 $$$r = 2$$$。我们可以看到 $$$\min(2, 1) + \max(2, 1) = 2 + 1 = 3$$$,这是奇数。因此,在同时为所有 $$$1 \le i \le 2$$$ 分配 $$$a_i := a_{3-i}$$$ 后,我们得到 $$$a = [1, 2, 3]$$$,这是非递减的。

考虑第四个测试用例,

  • 操作 1:选择$$$l = 1$$$,$$$r = 3$$$。该数组变为 $$$a = [2, 1, 4, 3, 3, 6]$$$。
  • 操作2:选择$$$l = 3$$$,$$$r = 5$$$。该数组变为 $$$a = [2, 1, 3, 3, 4, 6]$$$。
  • 操作3:选择$$$l = 1$$$,$$$r = 2$$$。该数组变为 $$$a = [1, 2, 3, 3, 4, 6]$$$。

对于第五个测试用例,请注意,不可能选择满足条件的索引 $$$l$$$ 和 $$$r$$$ 。因此,输出NO。