交换与删除

时间限制：2s
空间限制：512MB

题目描述

给定数列 $A=(A_1,A_2,\ldots,A_N)$。你可以任意次执行以下两种操作：

1. 选择相邻的两项并交换它们；
2. 选择一个非空前缀，要求前缀内所有数相等，然后把这个前缀整体删除。

求把数列删空所需的最少操作次数。有 $T$ 组测试数据，请分别求解。

输入格式

第一行输入一个整数 $T$。

每组数据先输入一个整数 $N$，下一行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

对每组数据输出一行一个整数，表示最少操作次数。

样例输入 1

3
5
1 1 2 1 2
4
4 2 1 3
11
1 2 1 2 1 2 1 2 1 2 1

样例输出 1

3
4
8

样例说明

第一组数据可以先交换原序列第 $3,4$ 项，得到 $(1,1,1,2,2)$，再分两次删除两个常值前缀，共使用 $3$ 次操作。

数据范围

• $1\le T\le 10^5$；
• $2\le N\le 2\times10^5$；
• $1\le A_i\le N$；
• 单个输入文件中所有 $N$ 之和不超过 $2\times10^5$。

附件数据

• 子任务 1：输入　输出
• 子任务 2：输入　输出
• 子任务 3：输入　输出
• 子任务 4：输入　输出
• 子任务 5：输入　输出