← 返回题目列表

Codeforces · 2112/B

B. 缩小数组

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

让我们调用一个数组 $$$b$$$ 美丽 如果它至少包含两个元素并且存在位置 $$$i$$$ 使得 $$$|b_i - b_{i + 1}| \le 1$$$ (其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值)。

给你一个数组$$$a$$$,只要它至少由两个元素组成,你就可以执行以下操作:

  1. 在数组 $$$a$$$ 中选择两个相邻位置 $$$i$$$ 和 $$$i + 1$$$。
  2. 选择一个整数 $$$x$$$,使得 $$$\min(a_i, a_{i + 1}) \le x \le \max(a_i, a_{i + 1})$$$。
  3. 从数组中删除数字 $$$a_i$$$ 和 $$$a_{i + 1}$$$,并在其位置插入数字 $$$x$$$。显然,数组的大小将减少$$$1$$$。

计算使数组美观所需的最少操作数,否则报告不可能。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) - 数组 $$$a$$$ 本身。

输出

对于每个测试用例,输出一个整数——使数组 $$$a$$$ 漂亮所需的最少操作数,如果不可能使其漂亮,则输出 $$$-1$$$ 。

示例

输入
复制

4
4
1 3 3 7
2
6 9
4
3 1 3 7
4
1 3 5 2

输出
复制

0
-1
1
1

注意

在第一个测试用例中,给定的数组已经很漂亮了,如 $$$|a_2 - a_3| = |3 - 3| = 0$$$。

在第二个测试用例中,不可能使数组变得漂亮,因为应用该操作会将其大小减少到小于 2。

在第三个测试用例中,您可以选择 $$$a_1$$$ 和 $$$a_2$$$ 并将它们替换为数字 $$$2$$$。生成的数组 $$$[2, 3, 7]$$$ 很漂亮。

在第四个测试用例中,您可以选择 $$$a_2$$$ 和 $$$a_3$$$ 并将它们替换为数字 $$$3$$$。生成的数组 $$$[1, 3, 2]$$$ 很漂亮。