← 返回题目列表

Codeforces · 1714/B

B. 删除前缀

中文机器翻译题面 查看原题

Polycarp 被呈现出一些长度为 $$$n$$$ 的整数序列 $$$a$$$ ($$$1 \le a_i \le n$$$)。只有当一个序列由不同的数字(即不同的数字)组成时,它才能让波利卡普高兴。

为了使他的序列像这样,波利卡普将进行一些(可能为零)的移动。

只需一招,他就能:

- 删除序列的第一个(最左边)元素。

例如,在一步操作中,序列 $$$[3, 1, 4, 3]$$$ 将生成序列 $$$[1, 4, 3]$$$,其中包含不同的数字。

确定他需要进行的最少移动次数,以便在剩余序列中所有元素都不同。换句话说,找到给定序列 $$$a$$$ 的最小前缀的长度,删除该前缀后序列中的所有值都将是唯一的。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成。

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 给定序列 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 给定序列 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,请在单独的行上打印您的答案 - 必须从序列开头删除的最小元素数,以便所有剩余元素都不同。

示例

输入 #1

5
4
3 1 4 3
5
1 1 1 1 1
1
1
6
6 5 4 3 2 1
7
1 2 1 7 1 2 1

输出 #1

1
4
0
0
5

注意

以下是删除前缀后保留的序列:

- $$$[1, 4, 3]$$$;
- $$$[1]$$$;
- $$$[1]$$$;
- $$$[6, 5, 4, 3, 2, 1]$$$;
- $$$[2, 1]$$$.

很容易看出,所有剩余序列仅包含不同的元素。在每个测试用例中,删除了最短的匹配前缀。