CF1416E Split

有一天，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$ 的方式。

输入文件的第一行包含一个整数 $T$（$1 \le T \le 5 \cdot 10^5$），表示测试用例的数量。接下来是 $T$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$2 \le a_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每组测试数据，输出一行一个整数，表示 $|b|$ 的最小可能值。

由 ChatGPT 4.1 翻译