Make an array
53% Success4768 Attempts20 Points1s Time Limit256MB Memory1024 KB Max Code

You are given an array A of length N. You take an array B of length N such that B[i] = 0 for each 1 <= i <= N. You can apply the following operation on B any number of times:

  • Choose (N - 1) distinct indices and add 1 to each of those indices.

Task

Find the number of operations required to convert array B into array A by applying the given operation. Print -1 if it is impossible to do so.

Function description

Complete the function solve() provided in the editor. This function takes the following two parameters and returns the required answer:

  • N: Represents the length of array A.
  • A: Represents the array A.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

  • The first line contains T, denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
  • For each test case:
    • The first line contains N, denoting the size of array A.
    • The second line contains N space-separated integers A[1], A[2], ....., A[N], denoting the elements of array A.

Output format
For each test case, print the number of operations required to convert array B into array A by applying the given operation or -1 if it is impossible to do so.

Constraints

\(1 \leq T \leq 10^4\)
\(2 \leq N \leq 10^5\)
\(0\leq A_i \le 10^{9}\)
\(\text{Sum of $N$ over all test cases does not exceed }2\cdot 10^5\)

Examples
Input
2
3
3 1 0
2
0 2
Output
-1
2
Explanation

The first line denotes T = 2.

For the first test case

Given

  • N = 3
  • A = [3, 1, 0]

​​Approach

  • It is impossible to convert B = [0, 0, 0] into A = [3, 1, 0] using the given operation. Thus, the answer is -1.

For the second test case

Given

  • N = 2
  • A = [0, 2]

​​Approach

  • Initially, B = [0, 0].
  • Applying the operation on index i = 2 makes B = [0, 1].
  • Applying the operation on index i = 2 makes B = [0, 2], which is equal to A. Thus, the answer is 2.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results