#P18634. Hard Problem

Hard Problem

Hard Problem

给定一个由非负整数构成的序列 a1,…,ana_1,\ldots,a_n。你可以任意次执行以下三种操作:

  1. 选择区间 [l,r][l,r],将其中的所有数减1。
  2. 选择区间 [l,r][l,r],将其中下标为奇数的数减1。
  3. 选择区间 [l,r][l,r],将其中下标为偶数的数减1。

求使所有数都变为0所需的最少操作次数。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含两行:

  • 第一行一个整数 nn。
  • 第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

对于每个测试用例,输出一行一个整数,表示最少操作次数。

数据范围

1≤T≤101\le T\le10。每个测试用例满足 1≤n≤1051\le n\le10^5,0≤ai≤1090\le a_i\le10^9。

没有额外的所有测试用例长度总和限制。下标从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