← 返回题目列表

Codeforces · 2143/A

A. 所有长度减法

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

给你一个长度为 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$。

您必须按顺序对从 1 到 $$$n$$$ 的每个整数 $$$k$$$ 执行一次操作:

  • 选择一个子数组$$$^{\text{†}}$$$,其长度为 $$$p$$$,长度恰好为 $$$k$$$,并从该子数组中的每个元素中减去 1。

完成所有 $$$n$$$ 操作后,您的目标是使数组的所有元素都为零。

确定是否可以实现这一目标。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

$$$^{\text{†}}$$$数组 $$$a$$$ 是数组 $$$b$$$ 的子数组,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

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

第一行包含值 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 排列的长度。

第二行包含 $$$p_1, p_2, \ldots p_n$$$ ($$$1 \le p_i \le n$$$) — 排列本身。

输出

对于每个测试用例,输出 是 执行完所有操作后是否可以使数组$$$p$$$的所有元素都等于$$$0$$$;否则,输出 NO.

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

示例

输入
复制

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

输出
复制

YES
NO
YES
NO

注意

对于第一个测试用例,我们可以按如下方式进行:

  • $$$k = 1$$$:选择子数组 $$$[3, 3]$$$。数组 $$$[1, 3, 4, 2]$$$ 变为 $$$[1, 3, 3, 2]$$$。
  • $$$k = 2$$$:选择子数组 $$$[2, 3]$$$。数组 $$$[1, 3, 3, 2]$$$ 变为 $$$[1, 2, 2, 2]$$$。
  • $$$k = 3$$$:选择子数组 $$$[2, 4]$$$。数组 $$$[1, 2, 2, 2]$$$ 变为 $$$[1, 1, 1, 1]$$$。
  • $$$k = 4$$$:选择子数组 $$$[1, 4]$$$。数组 $$$[1, 1, 1, 1]$$$ 变为 $$$[0, 0, 0, 0]$$$。

这样,我们就成功地将整个数组归零了,所以答案是 是.

对于第二个测试用例,可以证明不可能将所有元素减少到零。

对于第三个测试用例,流程如下:

$$$[2, 4, \boldsymbol{5}, 3, 1] \rightarrow [2, \boldsymbol{4, 4}, 3, 1] \rightarrow [2, \boldsymbol{3, 3, 3}, 1] \rightarrow [\boldsymbol{2, 2, 2, 2}, 1] \rightarrow [\boldsymbol{1, 1, 1, 1, 1}] \rightarrow [0, 0, 0, 0, 0].$$$

粗体值表示我们在每一步中从中减去的子数组。

对于第四个测试用例,也可以证明不可能将所有值都归零。