Stable Mex ~ Multiplex Coder

Chef gives you a sequence

A

of length

N

.
Let

X

denote the

M E X

of the sequence

A

. Chef is interested in the count of positive values

k

, such that, if every element

A_{i}

A

is replaced by

max (A_{i} - k, 0)

, the

M E X

of the sequence still remains

X

Find the count of such values. If there are infinite such values, print $- 1$

instead.

As a friendly reminder, the $M E X$

of a sequence is the smallest non-negative integer that does not belong to the sequence. For instance:

The $M E X$

[2, 2, 1]

0

because

0

does not belong to the sequence.

The

M E X

[3, 1, 0, 1]

2

because

0

and

1

belong to the sequence, but

2

does not.

Input Format

The first line of the input contains a single integer $T$

denoting the number of test cases. The description of

T

test cases follows.

The first line of each test case contains a single integer

N

- the length of the sequence

A

The second line of each test case contains

N

space-separated integers

A_{1}, A_{2}, \dots, A_{N}

Output Format

For each test case print a single integer — the count of positive values $k$

satisfying the given condition. If there are infinite such values, print

- 1

instead.

Constraints

$1 \leq T \leq 10^{4}$

1 \leq N \leq 10^{5}

0 \leq A_{i} \leq 10^{9}

Sum of

N

over all test cases does not exceed

2 \cdot 10^{5}

Sample Input 1

3
4
1 2 3 5
1
0
7
5 10 2 4 0 6 1

Sample Output 1

0
-1
1

Explanation

Test case $1$

: There doesn't exist any value of

k

satisfying the given condition.

Test case $2$

: There are infinite values of

k

satisfying the given condition.

Test case $3$

: There is only

1

value of

k

satisfying the given condition:

k = 4

. The

M E X

of the given sequence is

3

. When every element

A_{i}

of the given sequence is replaced by

m a x (A_{i} - 4, 0)

, the sequence becomes

[1, 6, 0, 0, 0, 2, 0]

, which also has

M E X = 3

Stable Mex