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

Prime List | GFG You are given the head of a linked list. You have to replace all the values of the nodes with
Minimum Coloring There is a matrix of size N×MN×M. Two distinct cells of the matrix (x1,y1
Yet Another Mex Problem Nayra doesn't like stories of people receiving random arrays as birthday presents, but this
Maximizing LIS Chef received an array AA of NN integers as a valentine's day present. He

Stable Mex