Description

Bob likes sequences.

There is a non-negative integer sequence $a_1, a_2,\cdots, a_n$ of length $n$. In each step, you may choose one of the following three operations to perform:

• Choose an interval $[l, r]$, and subtract $1$ from all numbers whose indices are in this interval.

• Choose an interval $[l, r]$, and subtract $1$ from all numbers in this interval whose indices are odd.

• Choose an interval $[l, r]$, and subtract $1$ from all numbers in this interval whose indices are even.

Find the minimum number of steps needed to make all numbers in the sequence become $0$.

Input Format

The first line contains an integer $T$, which denotes the number of test cases.

For each test case, the first line contains an integer $n$. The next line contains $n$ non-negative integers $a_1, a_2,\dots, a_n$.

Output Format

Output $T$ lines. For each test case, output one integer per line, which is the answer.

3
5
2 1 2 1 2
8
1000000000 1000000000 0 1000000000 1000000000 0 1000000000 1000000000
13
1 1 4 5 1 4 1 9 1 9 8 1 0

2
3000000000
19

Hint

Sample explanation $1$.

Test case 1: $21212 \stackrel{1}{\longrightarrow} 1111 1 \stackrel{1}{\longrightarrow} 00000$.

Test case 3: $1145141919810 \stackrel{1}{\longrightarrow} 0034030808700 \stackrel{8}{\longrightarrow} 0031000000700 \stackrel{10}{\longrightarrow}0000000000000$.

Sample input and output $2$ are provided in the attached file.

Constraints:

For the first $10\%$ of the testdata, $n \leq 5, a_i \leq 10$.

For the first $30\%$ of the testdata, $n \leq 50, a_i \leq 50$.

For the first $50\%$ of the testdata, $n \leq 200, a_i \leq 200$.

For the first $60\%$ of the testdata, $n \leq 200, a_i \leq 10^9$.

For the first $70\%$ of the testdata, $n \leq 1000, a_i \leq 10^9$.

For the first $90\%$ of the testdata, $n \leq 10000, a_i \leq 10^9$.

For $100\%$ of the testdata, $1 \leq n \leq 100000, 0 \leq a_i \leq 10^9, 1 \leq T \leq 10$.

Translated by ChatGPT 5