Problem D - Marble Game

Problem D
Marble Game
Input: Standard Input

Output: Standard Output

You and your friend are playing a game. The game field contains n boxes arranged in a circle. The boxes are numbered from 0 to n-1. i’th box has 2 adjacent box. Box (i+1) mod n is its adjacent in clockwise direction while box (i-1+n) mod n is its adjacent in anticlockwise direction. In each move you and your friend select 2 marble. You move your selected marble in clockwise direction while your friend move his selected marble in anticlockwise direction simultaneously. The goal of the game is to move all the marbles in a single cell. A cell is a valid destination if you can move all the marbles to that cell by following the rules of the game. Also for each valid destination you can move all the marbles to there in minimum number of moves. You have to calculate the sum of all these minimum number of moves.

Input
First line contains T(1≤T≤120) the number of test cases. Each test case contains 2 lines. First line contains n(1≤n≤50000) the number of boxes. Second line contains n non-negative integers. The i’th integer denotes the number of marbles in box i. Each box can have at most 10000 marble initially. For each test case the total number of marble is positive.

Output
For each test case output contains 2 integers separated by a single space. The first integer is the number of valid destination cells and the second integer is sum of minimum number of moves to all these valid destinations. The input will be such that the second integer will fit 64 bit signed integer.

Sample Input Output for Sample Input

1 1 1

0 1 1 1

2 1 2 1

3 3

1 1

2 6

Problemsetter: Abdullah al Mahmud (Satej)

Special Thanks: Derek Kisman