给定一个由整数组成的序列 $$$a_1, a_2, \dots, a_n$$$。
您可以对此序列应用以下操作:选择某个整数 $$$x$$$ 并将所有等于 $$$x$$$ 的元素移动到 $$$a$$$ 的开头或结尾。请注意,您必须在一次操作中向一个方向移动所有这些元素。
例如,如果 $$$a = [2, 1, 3, 1, 1, 3, 2]$$$,则可以通过一次操作得到以下序列(为方便起见,将等于 $$$x$$$ 的元素表示为 $$$x$$$-元素):
- $$$[1, 1, 1, 2, 3, 3, 2]$$$ 如果将所有 $$$1$$$ 元素移动到开头;
- $$$[2, 3, 3, 2, 1, 1, 1]$$$ 如果将所有 $$$1$$$ 元素移动到末尾;
- $$$[2, 2, 1, 3, 1, 1, 3]$$$ 如果将所有 $$$2$$$ 元素移动到开头;
- $$$[1, 3, 1, 1, 3, 2, 2]$$$ 如果将所有 $$$2$$$ 元素移动到末尾;
- $$$[3, 3, 2, 1, 1, 1, 2]$$$ 如果将所有 $$$3$$$-元素移动到开头;
- $$$[2, 1, 1, 1, 2, 3, 3]$$$ 如果将所有 $$$3$$$-元素移动到末尾;
您必须确定此类操作的最小数量,以便序列 $$$a$$$ 按非降序排序。非降序意味着对于从 $$$2$$$ 到 $$$n$$$ 的所有 $$$i$$$,满足条件 $$$a_{i-1} \le a_i$$$。
请注意,您必须回答 $$$q$$$ 独立查询。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询的数量。每个查询由连续的两行表示。
每个查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 元素的数量。
每个查询的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le n$$$) - 元素。
保证所有 $$$n$$$ 的总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个查询,打印一个整数 - 以非降序排列序列 $$$a$$$ 的最小操作次数。
示例
输入 #1
3 7 3 1 6 6 3 1 1 8 1 1 4 4 4 7 8 8 7 4 2 5 2 6 2 7
输出 #1
2 0 1
注意
在第一个查询中,您可以将所有 $$$1$$$ 元素移动到开头(该序列之后变成 $$$[1, 1, 1, 3, 6, 6, 3]$$$),然后将所有 $$$6$$$ 元素移动到末尾。
在第二个查询中,序列最初已排序,因此答案为零。
在第三个查询中,您必须将所有 $$$2$$$ 元素移动到开头。