CF1416E.Split

One day, BThero decided to play around with arrays and came up with the following problem:

You are given an array $a$, which consists of $n$ positive integers. The array is numerated $1$ through $n$. You execute the following procedure exactly once:

• You create a new array $b$ which consists of $2n$ positive integers, where for each $1 \le i \le n$ the condition $b_{2i-1}+b_{2i} = a_i$ holds. For example, for the array $a = [6, 8, 2]$ you can create $b = [2, 4, 4, 4, 1, 1]$.
• You merge consecutive equal numbers in $b$. For example, $b = [2, 4, 4, 4, 1, 1]$ becomes $b = [2, 4, 1]$.

Find and print the minimum possible value of $|b|$ (size of $b$) which can be achieved at the end of the procedure. It can be shown that under the given constraints there is at least one way to construct $b$.

有一天，BThero 决定玩弄数组，并提出了以下问题：

给你一个由 $n$ 个正整数组成的数组 $a$，数组下标从 $1$ 到 $n$。你恰好执行以下过程一次：

• 构造一个由 $2n$ 个正整数组成的新数组 $b$，使得对每个 $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$。

The first line of the input file contains a single integer $T$ ($1 \le T \le 5 \cdot 10^5$) denoting the number of test cases. The description of $T$ test cases follows.

The first line of each test contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line contains $n$ space-separated integers $a_1$, $a_2$, ..., $a_n$ ($2 \le a_i \le 10^9$).

It is guaranteed that $\sum{n}$ over all test cases does not exceed $5 \cdot 10^5$.

输入文件的第一行包含一个整数 $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$）。

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

For each test case, print a single line containing one integer — the minimum possible value of $|b|$.

对于每个测试用例，输出一行，包含一个整数——$|b|$ 的最小可能值。