← 返回题目列表

Codeforces · 1416/E

E. 分裂

中文机器翻译题面 查看原题

有一天,BThero 决定尝试一下数组,并提出了以下问题:

给定一个数组 $$$a$$$,它由 $$$n$$$ 正整数组成。该数组从 $$$1$$$ 到 $$$n$$$ 进行编号。您只需执行一次以下过程:

- 您创建一个新数组 $$$b$$$,其中包含 $$$2n$$$ 正整数,其中对于每个 $$$1 \le i \le n$$$,条件 $$$b_{2i-1}+b_{2i} = a_i$$$ 成立。例如,对于数组 $$$a = [6, 8, 2]$$$,您可以创建 $$$b = [2, 4, 4, 4, 1, 1]$$$。
- 您合并 $$$b$$$ 中连续的相等数字。例如,$$$b = [2, 4, 4, 4, 1, 1]$$$ 变为 $$$b = [2, 4, 1]$$$。

查找并打印在过程结束时可以达到的 $$$|b|$$$ 的最小可能值($$$b$$$ 的大小)。可以证明,在给定的约束下,至少有一种构造$$$b$$$的方法。

输入

输入文件的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 5 \cdot 10^5$$$) 表示测试用例的数量。 $$$T$$$ 测试用例的描述如下。

每个测试的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$2 \le a_i \le 10^9$$$)。

保证所有测试用例的 $$$\sum{n}$$$ 不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,打印一行包含一个整数 - $$$|b|$$$ 的最小可能值。

示例

输入 #1

3
3
6 8 2
1
4
3
5 6 6

输出 #1

3
1
2