[ZJOI2020] 序列
题目背景
1s,512MB
题目描述
Bob 喜欢序列。
有一个长度为 $n$ 的非负整数序列 $a_1, a_2,\cdots, 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 \stackrel{1}{\longrightarrow} 1111 1 \stackrel{1}{\longrightarrow} 00000$
第三组数据:$1145141919810 \stackrel{1}{\longrightarrow} 0034030808700 \stackrel{8}{\longrightarrow} 0031000000700 \stackrel{10}{\longrightarrow}0000000000000$
样例输入输出 $2$ 见下发文件
对于前 $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 ai \leq 10^9, 1 \leq T \leq 10$。