More Garden Troubles

Interview

Time limit2sMemory limit128 MB

Summary

Find the fewest flamethrower shots that clear every plot when each shot halves a plot and its two neighbors, rounding down.

Level: Medium5 of 10
Topics: Greedy, Math, Array
Solved: No attempts yet

Problem

Mr. Wincenty owns a garden and is famously the sort of person who cannot stand yard work. Some time after his earlier troubles with fallen leaves, spring arrived and brought a new headache: weeds began sprouting all over the garden. One day, after long hours in his workshop, Mr. Wincenty walked into the garden holding a portable flamethrower.

The garden consists of $N$ plots numbered from $1$ to $N$ . Plot $i$ holds a whole number of weeds $c_i$ . Firing the flamethrower once at plot $i$ halves the number of weeds in plot $i$ and in the neighboring plots $i-1$ and $i+1$ .

Here "halving" means integer division by $2$ (rounding down): $8$ weeds become $4$ , and $5$ weeds become $2$ . You may also aim the flamethrower at the non-existent plots $0$ or $N+1$ ; in that case only plot $1$ or only plot $N$ is reduced, respectively.

Determine the minimum number of times Mr. Wincenty must fire the flamethrower so that every plot ends up with $0$ weeds.

Input

The first line contains an integer $Z$ ( $1 \le Z \le 10$ ), the number of test cases. The test cases follow.

Each test case begins with a line containing one integer $N$ ( $1 \le N \le 10^6$ ), the number of plots in the garden. The next line contains $N$ space-separated integers $c_i$ ( $0 \le c_i \le 10^6$ ), the number of weeds in each plot.

Output

For each test case, print on its own line the minimum number of times the flamethrower must be used.

Examples4

Example 1
Input
```
3 
1 
1 
3 
4 2 4 
5 
2 0 0 0 2
```
Expected output
```
1
3
4
```
Example 2
Input
```
1
5
0 0 0 0 0
```
Expected output
```
0
```
Example 3
Input
```
1
1
1000000
```
Expected output
```
20
```
Example 4
Input
```
1
4
5 6 7 8
```
Expected output
```
7
```