「ZJOI2020」序列

题目描述

Bob 喜欢序列。

有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$。每一步你可以从以下三种操作中选择一种执行：

• 选择一个区间 $[l, r]$，将下标在这个区间里的所有数都减 $1$。
• 选择一个区间 $[l, r]$，将下标在这个区间里且下标为奇数的所有数都减 $1$。
• 选择一个区间 $[l, r]$，将下标在这个区间里且下标为偶数的所有数都减 $1$。

求最少需要多少步才能将序列中的所有数都变成 $0$。

输入格式

第一行输入一个整数 $T$，表示数据组数。

对于每组数据，第一行输入一个整数 $n$，接下来一行输入 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。

输出格式

输出 $T$ 行，对于每组测试数据，输出一行一个整数，表示答案。

样例

输入

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

样例解释

第一组数据： $2\ 1\ 2\ 1\ 2 \xrightarrow{1} 1\ 1\ 1\ 1\ 1 \xrightarrow{1} 0\ 0\ 0\ 0\ 0$

第三组数据： $1\ 1\ 4\ 5\ 1\ 4\ 1\ 9\ 1\ 9\ 8\ 1\ 0 \xrightarrow{1} 0\ 0\ 3\ 4\ 0\ 3\ 0\ 8\ 0\ 8\ 7\ 0\ 0 \xrightarrow{8} 0\ 0\ 3\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 7\ 0\ 0 \xrightarrow{10} 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0$

数据范围与提示

• 对于前 $10\%$ 的数据，$n \leq 5, a_i \leq 10$
• 对于前 $30\%$ 的数据，$n \leq 50, a_i \leq 50$
• 对于前 $50\%$ 的数据，$n \leq 200, a_i \leq 200$
• 对于前 $60\%$ 的数据，$n \leq 200, a_i \leq 10^9$
• 对于前 $70\%$ 的数据，$n \leq 1000, a_i \leq 10^9$
• 对于前 $90\%$ 的数据，$n \leq 10000, a_i \leq 10^9$
• 对于 $100\%$ 的数据，$1 \leq n \leq 100000, 0 \leq a_i \leq 10^9, 1 \leq T \leq 10$