#P18634. Hard Problem
Hard Problem
Hard Problem
给定一个由非负整数构成的序列 。你可以任意次执行以下三种操作:
- 选择区间 ,将其中的所有数减1。
- 选择区间 ,将其中下标为奇数的数减1。
- 选择区间 ,将其中下标为偶数的数减1。
求使所有数都变为0所需的最少操作次数。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例包含两行:
- 第一行一个整数 。
- 第二行 个整数 。
输出格式
对于每个测试用例,输出一行一个整数,表示最少操作次数。
数据范围
。每个测试用例满足 ,。
没有额外的所有测试用例长度总和限制。下标从1开始。
样例输入 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