MATH1 - Math I

You are given n integers a1, a2 ... an (0<=ai<=n). The sum a1 + a2 + ... + an does not exceeded n. Your task is to find n other integers x1, x2 ... xn (note that xi may be negative numbers) satisfying the following conditions:

  • (xi - xi+1 + ai+1 = 0) or (xi - xi+1 + ai+1 = 1) for i=1..n-1
  • (xn - x1 + a1 = 0) or (xn - x1 + a1 = 1)
  • |x1|+|x2|+ ... +|xn| is minimized

Input

The first line of the input file contains an integer t representing the number of test cases (t<=20). Then t test cases follow. Each test case has the following form:

  • The first line contains n (1<=n<=1000)
  • The second line contains n integers a1, a2 ... an separated by single spaces

Output

For each test case output a single value: the minimum value of |x1|+|x2|+ ... +|xn|

Example

Input:
2
4
2 1 0 0
5
0 1 2 2 0

Output:
1
3

Explanation

In the former case, the optimal solution is (x1=0, x2=0, x3=0, x4=-1)

In the latter case, the optimal solution is (x1=-1, x2=-1, x3=0, x4=1, x5=0)


Added by:Jimmy
Date:2005-05-25
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET

hide comments
2023-10-10 13:58:04
Any help?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.