独特数组

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

题目描述

给定一个长度为 $n$ 的整数序列 $a$。称 $a$ 的一个连续子序列为它的一个子段，即对于满足 $1\le l<r\le n$ 的整数 $l,r$，序列 $[a_l,a_{l+1},\ldots,a_r]$ 是一个子段。

若一个子段中存在某个整数恰好出现一次，则称这个子段为独特子段。

你可以进行任意次操作：选择序列中的一个元素，并将它替换为任意整数。

求使序列 $a$ 的每个子段都成为独特子段所需的最少操作次数。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每个测试用例，输出一行一个整数，表示最少操作次数。

样例输入 1

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

样例输出 1

0
2
1
0

数据范围

对于所有数据，$1\le t\le 10^4$，$1\le n\le 3\times10^5$，$1\le a_i\le n$，且所有测试用例的 $n$ 之和不超过 $3\times10^5$。

提示

对于第二组样例，可以替换第一个和第三个元素，例如得到 $[3,4,1,4]$。

对于第三组样例，可以替换第四个元素，例如得到 $[3,1,2,3,2]$。