CF2226D Reserved Reversals

给定一个由 $n$ 个正整数组成的数组 $a$。 对于数组中从第 $l$ 个位置到第 $r$ 个位置的任意一段（$1 \le l \le r \le n$），记 $m(l, r)$ 表示该区间的最小值，$M(l, r)$ 表示最大值。形式化地， $$ \begin{aligned} 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{aligned} $$ 你可以执行以下操作任意次（也可以一次都不执行）： - 选择两个下标 $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$ 变为非降数组$^\ast$。 $^\ast$一个数组 $[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$ 变为非降数组，输出 "YES"；否则输出 "NO"。 输出时不区分大小写，例如 "yEs"、"yes"、"Yes" 和 "YES" 均视为正答。

对于第一个测试用例，数组已经是非降的，因此输出 YES。 对于第二个测试用例，取 $l=1$，$r=2$，有 $\min(2, 1) + \max(2, 1) = 2 + 1 = 3$，为奇数。经过 $a_i := a_{3-i}$（$1 \le i \le 2$）赋值后，得到 $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。 由 ChatGPT 5 翻译