## MATH1 - Math I

no tags

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

Output Details:
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: Duc Date: 2005-05-25 Time limit: 20s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS PERL6 VB.NET