← 返回题目列表

Codeforces · 1340/A

A. 纳斯蒂亚和奇怪的发电机

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

丹尼斯在娜斯佳拒绝他后非常难过。于是他决定穿过大门去找点乐子。幸运之神向他微笑了!当他进入第一个庭院时,他遇到了一个正在卖东西的陌生男子。

丹尼斯买了一件神秘物品,它是......随机排列生成器!丹尼斯简直不敢相信自己的运气。

回到家后,他开始研究发电机的工作原理并学习算法。生成排列的过程由 $$$n$$$ 个步骤组成。在第$$$i$$$步骤中,为数字$$$i$$$$$$(1\leq i\leq n)$$$选择一个位置。数字 $$$i$$$ 的位置定义如下:

- 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$j$$$,我们计算 $$$r_j$$$ — 满足 $$$j \leq r_j \leq n$$$ 的最小索引,并且位置 $$$r_j$$$ 尚未在排列中占据。如果没有这样的位置,那么我们假设 $$$r_j$$$ 的值未定义。
- 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$t$$$,我们计算 $$$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$$$ 达到最大值,因此算法将为数字 $$$4$$$ 唯一选择此位置。

丹尼斯对购买的产品感到满意,回家了。他连续几天不间断地进行排列。他相信他可以想出不比生成器差的随机排列。之后,他写出了想到的第一个排列 $$$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$$$。

输出

如果可以通过生成器获得此排列,则打印“是”。否则,打印“否”。

任何情况下都可以显示所有字母。

示例

输入 #1

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

输出 #1

Yes
Yes
No
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$$$位置达到,因此生成器将选择该位置。

在 $$$4$$$ 步骤,$$$r = [3, 3, 3, 4, \times],count = [0, 0, 3, 1, 0]$$$。最大值为$$$3$$$并且仅在$$$3$$$位置处达到,因此生成器将选择该位置。

在 $$$5$$$ 步骤,$$$r = [4, 4, 4, 4, \times],count = [0, 0, 0, 4, 0]$$$。最大值为$$$4$$$并且仅在$$$4$$$位置处达到,因此生成器将选择该位置。

总共,我们得到了 $$$2, 3, 4, 5, 1$$$ 的排列,也就是说,生成器可以生成它。