题目描述

给定三个数组 $a$、$b$ 和 $c$。初始时，数组 $a$ 包含 $n$ 个元素，数组 $b$ 和 $c$ 为空。

您正在执行以下算法，该算法包括两个步骤：

步骤 1：只要 $a$ 不为空，您就从 $a$ 中取出最后一个元素并将其移动到数组 $b$ 的中间。如果 $b$ 的长度为奇数，则可以选择：将元素从 $a$ 放置在 $b$ 的中间元素的左侧或右侧。最终，$a$ 变为空，$b$ 由 $n$ 个元素组成。

步骤 2：只要 $b$ 不为空，您就取出 $b$ 的中间元素并将其移动到数组 $c$ 的末尾。如果 $b$ 的长度为偶数，则可以选择两个中间元素中的其中一个。结果，$b$ 变为空，$c$ 现在由 $n$ 个元素组成。

参见注释部分的示例。

您能使数组 $c$ 按非递减顺序排序吗？

输入格式

第一行包含一个整数 $t(1≤t≤2⋅10^4)$——测试用例的数量。接下来是 $t$ 个测试用例。

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

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^6)$——数组 $a$ 本身。

保证 $n$ 的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，如果您能使数组 $c$ 按非递减顺序排序，则输出 YES（不区分大小写）。否则，输出 NO（不区分大小写）。

测试样例

3
4
3 1 5 3
3
3 2 1
1
7331

YES
NO
YES

样例说明

在第一个测试用例中，我们可以针对 $a=[3,1,5,3]$ 进行如下操作：

步骤 1：

$a [3,1,5,3] ⇒ [3,1,5] ⇒ [3,1] ⇒ [3] ⇒ []$

$b [] ⇒ [3] ⇒ [3,5] ⇒ [3,1,5] ⇒ [3,3,1,5]$

步骤 2：

$b [3,3,1,5] ⇒ [3,3,5] ⇒ [3,5] ⇒ [5] ⇒ []$

$c [] ⇒ [1] ⇒ [1,3] ⇒ [1,3,3] ⇒ [1,3,3,5]$

因此，数组 $c=[1,3,3,5]$，且已排序。