[Solution] Andrew and Stones solution codeforces

Andrew and Stones solution codeforces – Andrew has 𝑛n piles with stones. The 𝑖i-th pile contains 𝑎𝑖ai stones. He wants to make his table clean so he decided to put every stone either to the 11-st or the 𝑛n-th pile.

Andrew can perform the following operation any number of times: choose 33 indices 1𝑖<𝑗<𝑘𝑛1≤i<j<k≤n, such that the 𝑗j-th pile contains at least 22 stones, then he takes 22 stones from the pile 𝑗j and puts one stone into pile 𝑖i and one stone into pile 𝑘k.

Tell Andrew what is the minimum number of operations needed to move all the stones to piles 11 and 𝑛n, or determine if it’s impossible.

Andrew and Stones solution codeforces

The input contains several test cases. The first line contains one integer 𝑡t (1𝑡100001≤t≤10000) — the number of test cases.

The first line for each test case contains one integer 𝑛n (3𝑛1053≤n≤105) — the length of the array.

The second line contains a sequence of integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — the array elements.

It is guaranteed that the sum of the values 𝑛n over all test cases does not exceed 105105.

Output

For each test case print the minimum number of operations needed to move stones to piles 11 and 𝑛n, or print 1−1 if it’s impossible.

Example
input

Copy
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2

Andrew and Stones solution codeforces

4
-1
1
-1 

Andrew and Stones solution codeforces Note

In the first test case, it is optimal to do the following:

  1. Select (𝑖,𝑗,𝑘)=(1,2,5)(i,j,k)=(1,2,5). The array becomes equal to [2,0,2,3,7][2,0,2,3,7].
  2. Select (𝑖,𝑗,𝑘)=(1,3,4)(i,j,k)=(1,3,4). The array becomes equal to [3,0,0,4,7][3,0,0,4,7].
  3. Twice select (𝑖,𝑗,𝑘)=(1,4,5)(i,j,k)=(1,4,5). The array becomes equal to [5,0,0,0,9][5,0,0,0,9]. This array satisfy the statement, because every stone is moved to piles 11 and 55.

There are 44 operations in total.In the second test case, it’s impossible to put all stones into piles with numbers 11 and 33:

  1. At the beginning there’s only one possible operation with (𝑖,𝑗,𝑘)=(1,2,3)(i,j,k)=(1,2,3). The array becomes equal to [2,1,2][2,1,2].
  2. Now there is no possible operation and the array doesn’t satisfy the statement, so the answer is 1−1.

In the third test case, it’s optimal to do the following:

  1. Select (𝑖,𝑗,𝑘)=(1,2,3)(i,j,k)=(1,2,3). The array becomes equal to [2,0,2][2,0,2]. This array satisfies the statement, because every stone is moved to piles 11 and 33.

The is 11 operation in total.In the fourth test case, it’s impossible to do any operation, and the array doesn’t satisfy the statement, so the answer is 1−1.

 

Leave a Comment