让我们调用一个数组 $$$b$$$ 美丽 如果它至少包含两个元素并且存在位置 $$$i$$$ 使得 $$$|b_i - b_{i + 1}| \le 1$$$ (其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值)。
给你一个数组$$$a$$$,只要它至少由两个元素组成,你就可以执行以下操作:
- 在数组 $$$a$$$ 中选择两个相邻位置 $$$i$$$ 和 $$$i + 1$$$。
- 选择一个整数 $$$x$$$,使得 $$$\min(a_i, a_{i + 1}) \le x \le \max(a_i, a_{i + 1})$$$。
- 从数组中删除数字 $$$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$$$ 。
示例
输入复制
441 3 3 726 943 1 3 741 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]$$$ 很漂亮。