题目描述

序列 $b$ 是美丽的，当且仅当 $b$ 的长度至少为 $2$ 且存在一个位置 $i$ 使得 $\vert b_i-b_{i+1}\vert\le 1$。

给你一个序列 $a$，你可以执行以下操作直到其长度少于 $2$。

• 选择 $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$。这会使得 $a$ 的长度减少 $1$。

计算最少需要多少次操作使得 $a$ 变得美丽，或报告这是不可能的。

输入格式

多组数据。第一行一个整数 $t(1\le t\le 200)$，表示数据组数。

对于每组数据，第一行一个整数 $n(2\le n\le 1000)$，表示 $a$ 的大小。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le 10^6)$。

输出格式

对于每组数据，如果可以通过操作使得 $a$ 为美丽的，输出一行一个整数表示答案；否则输出一行 $-1$ 表示无解。

说明/提示

样例解释

对于第一组数据，$\vert a_2-a_3\vert=\vert 3-3\vert=0$，因此 $a$ 是美丽的。

对于第二组数据，执行操作会让 $a$ 的长度小于 $2$，所以不可能使得 $a$ 美丽。

对于第三组数据，选择 $a_1,a_2$ 和 $x=2$，操作后的序列 $[2,3,7]$ 是美丽的。

对于第四组数据，选择 $a_2,a_3$ 和 $x=3$，操作后的序列 $[1,3,2]$ 是美丽的。

样例

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

0
-1
1
1