#3313. 「ZJOI2020」序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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 行,对于每组测试数据,输出一行一个整数,表示答案。

样例

样例输入 1

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

样例输出 1

2
3000000000
19

样例解释 1

第一组数据: 21212 \xrightarrow{1} 11111 \xrightarrow{1} 00000

第三组数据: 1145141919810\xrightarrow{1}0034030808700\xrightarrow{8}0031000000700\xrightarrow{10}0000000000000

样例 2

见附加文件中 seq2.inseq2.out

数据范围与提示

对于前 10\% 的数据, n\le 5, a_i\le 10

对于前 30\% 的数据, n\le 50, a_i\le 50

对于前 50\% 的数据, n\le 200, a_i\le 200

对于前 60\% 的数据, n\le 200, a_i\le 10^9

对于前 70\% 的数据, n\le 1000, a_i\le 10^9

对于前 90\% 的数据, n\le 10000, a_i\le 10^9

对于 100\% 的数据, 1\le n\le 100000, 0\le a_i\le 10^9, 1\le T\le 10