CF1340A Nastya and Strange Generator

Denis 在被 Nastya 拒绝后非常伤心，于是他决定去门洞里散步找点乐子。幸运之神眷顾了他！当他走进第一个院子时，遇到了一位正在卖东西的奇怪男子。 Denis 买了一个神秘物品，结果竟然是……随机排列生成器！Denis 简直不敢相信自己的好运。 回到家后，他开始研究这个生成器的工作原理，并了解了其算法。生成一个排列的过程包含 $n$ 步。在第 $i$ 步时，会为数字 $i$（$1 \leq i \leq n$）选择一个位置。数字 $i$ 的位置选择规则如下： - 对于所有 $j$ 从 $1$ 到 $n$，我们计算 $r_j$ —— 这是满足 $j \leq r_j \leq n$ 且排列中位置 $r_j$ 尚未被占用的最小下标。如果不存在这样的 $r_j$，则认为 $r_j$ 未定义。 - 对于所有 $t$ 从 $1$ 到 $n$，我们计算 $count_t$ —— 表示有多少个 $1 \leq j \leq n$ 满足 $r_j$ 已定义且 $r_j = t$。 - 在排列中尚未被占用的位置中，找出 $count$ 数组值最大的那些位置。 - 生成器会在这些位置中任选一个，将数字 $i$ 放入。生成器可以任选其中任意一个位置。 让我们通过下面的例子来看看算法的运行过程：  设 $n = 5$，且算法已经将数字 $1, 2, 3$ 安排进了排列。考虑生成器如何为数字 $4$ 选择位置： - $r$ 的值为 $r = [3, 3, 3, 4, \times]$，其中 $\times$ 表示未定义。 - $count$ 的值为 $count = [0, 0, 3, 1, 0]$。 - 排列中仅剩两个未被占用的位置：$3$ 和 $4$。在 $count$ 数组中，位置 $3$ 的值为 $3$，位置 $4$ 的值为 $1$。 - 最大值只在位置 $3$ 处取得，因此算法会唯一地选择位置 $3$ 来放置数字 $4$。 Denis 对自己的购买非常满意，回家后连续几天不停地生成排列。他相信自己也能想出不逊于生成器的随机排列。于是，他随手写下了第一个想到的排列 $p_1, p_2, \ldots, p_n$，并想知道这个排列是否有可能通过上述生成器生成。 不幸的是，这个问题对他来说太难了，于是他向你求助。你需要判断，给定的排列是否可能通过描述的算法生成（假设生成器每次都能选择 Denis 需要的位置）。

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示排列的大小。 每个测试用例的第二行包含 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示 Denis 写下的排列。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

如果该排列可能是生成器生成的结果，输出 "Yes"；否则输出 "No"。 字母大小写不限。

让我们模拟一下生成器在第一个测试用例中的操作。 第 $1$ 步，$r = [1, 2, 3, 4, 5], count = [1, 1, 1, 1, 1]$。最大值在所有空位都能取得，因此生成器可以任选 $1$ 到 $5$ 号位置。在例子中，选择了 $5$。 第 $2$ 步，$r = [1, 2, 3, 4, \times], count = [1, 1, 1, 1, 0]$。最大值在 $1$ 到 $4$ 号位置都能取得，生成器可以任选其一。在例子中，选择了 $1$。 第 $3$ 步，$r = [2, 2, 3, 4, \times], count = [0, 2, 1, 1, 0]$。最大值为 $2$，只在位置 $2$ 取得，因此生成器会选择位置 $2$。 第 $4$ 步，$r = [3, 3, 3, 4, \times], count = [0, 0, 3, 1, 0]$。最大值为 $3$，只在位置 $3$ 取得，因此生成器会选择位置 $3$。 第 $5$ 步，$r = [4, 4, 4, 4, \times], count = [0, 0, 0, 4, 0]$。最大值为 $4$，只在位置 $4$ 取得，因此生成器会选择位置 $4$。 最终得到的排列为 $2, 3, 4, 5, 1$，即生成器可以生成该排列。 由 ChatGPT 4.1 翻译