← 返回题目列表

Codeforces · 2127/A

A. 混合墨西哥最大

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

给定一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$。然而$$$a$$$缺少一些元素,它们用$$$−1$$$表示。

我们定义数组 $$$a$$$ 是 好 当且仅当以下情况对于每个 $$$1 \leq i \leq n-2$$$ 成立:

$$\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = \max([a_i, a_{i+1}, a_{i+2}]) - \min([a_i, a_{i+1}, a_{i+2}]),$$

其中 $$$\operatorname{mex}(b)$$$ 表示 $$$b$$$ 中整数的最小排除 (MEX)$$$^{\text{*}}$$$。

你必须确定你是否可以赚到$$$a$$$ 好 将 $$$a$$$ 中的每个 $$$-1$$$ 替换为非负整数后。

$$$^{\text{*}}$$$整数集合 $$$b_1, b_2, \ldots, b_k$$$ 的最小排除 (MEX) 被定义为集合 $$$b$$$ 中不出现的最小非负整数 $$$x$$$。 例如,$$$\operatorname{mex}([2,2,1])=0$$$,因为$$$0$$$不属于数组,$$$\operatorname{mex}([0,3,1,2])=4$$$,因为$$$0$$$、$$$1$$$、$$$2$$$和$$$3$$$出现在数组中,但$$$4$$$出现在数组中没有。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 100$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-1 \leq a_i \leq 100$$$) — $$$a$$$ 的元素。 $$$a_i = -1$$$ 表示缺少该元素。

输出

对于每个测试用例,输出“是“如果可以制作$$$a$$$ 好和“NO”否则。

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

示例

输入
复制

8
3
-1 -1 -1
5
1 1 1 1 0
6
5 5 1 -1 -1 1
4
-1 -1 0 -1
4
-1 1 1 -1
3
3 3 -1
5
0 0 0 0 0
7
3 0 1 4 -1 2 3

输出
复制

YES
NO
NO
NO
YES
YES
NO
NO

注意

在第一个测试用例中,我们可以输入 $$$a_1 = a_2 = a_3 = 1$$$。然后,

  • $$$\operatorname{mex}([a_1, a_2, a_3]) = \operatorname{mex}([1, 1, 1]) = 0$$$;
  • $$$\max([a_1, a_2, a_3]) = \max([1, 1, 1]) = 1$$$;
  • $$$\min([a_1, a_2, a_3]) = \min([1, 1, 1]) = 1$$$。

且 $$$0 = 1 - 1$$$。因此,数组 $$$a$$$ 是 好.

在第二个测试用例中,$$$a$$$ 中没有缺少任何元素。我们有

  • $$$\operatorname{mex}([a_1, a_2, a_3]) = \max([a_1, a_2, a_3]) - \min([a_1, a_2, a_3])$$$,
  • $$$\operatorname{mex}([a_2, a_3, a_4]) = \max([a_2, a_3, a_4]) - \min([a_2, a_3, a_4])$$$,但是
  • $$$\operatorname{mex}([a_3, a_4, a_5]) \ne \max([a_3, a_4, a_5]) - \min([a_3, a_4, a_5])$$$。

因此,数组 $$$a$$$ 不能 好.

在第三个测试用例中,$$$a_1$$$、$$$a_2$$$ 或 $$$a_3$$$ 均不丢失。然而,

  • $$$\operatorname{mex}([a_1, a_2, a_3]) = \operatorname{mex}([5, 5, 1]) = 0$$$;
  • $$$\max([a_1, a_2, a_3]) = \max([5, 5, 1]) = 5$$$;
  • $$$\min([a_1, a_2, a_3]) = \min([5, 5, 1]) = 1$$$。

和 $$$0\ne 5 - 1$$$。所以数组 $$$a$$$ 不能是 好,无论您如何替换丢失的元素。