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]$$$.
很容易看出,所有剩余序列仅包含不同的元素。在每个测试用例中,删除了最短的匹配前缀。