分拆与合并

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定一个由 $n$ 个正整数组成的数组 $a$。对每个 $1\le i\le n$，把 $a_i$ 拆成两个正整数 $b_{2i-1},b_{2i}$，满足

然后，把 $b$ 中每一段连续相等的数合并成一个数。请最小化合并后数组的长度。

输入格式

第一行一个整数 $T$，表示测试数据组数。

每组数据第一行一个整数 $n$，第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组数据输出一行一个整数，表示合并后数组长度的最小值。

样例输入 1

3
3
6 8 2
1
4
3
5 6 6

样例输出 1

3
1
2

数据范围

对所有数据，$1\le T\le5\times10^5$，$1\le n\le5\times10^5$，$2\le a_i\le10^9$，且单个输入文件中 $\sum n\le5\times10^5$。

题目来源：Codeforces 1416E。