CF 1714B - Remove Prefix

Polycarp was presented with some sequence of integers a of length n (1≤ai≤n). A sequence can make Polycarp happy only if it consists of different numbers (i.e. distinct numbers).

In order to make his sequence like this, Polycarp is going to make some (possibly zero) number of moves.

In one move, he can:

remove the first (leftmost) element of the sequence.

For example, in one move, the sequence [3,1,4,3] will produce the sequence [1,4,3], which consists of different numbers.

Determine the minimum number of moves he needs to make so that in the remaining sequence all elements are different. In other words, find the length of the smallest prefix of the given sequence a, after removing which all values in the sequence will be unique.

Input

The first line of the input contains a single integer t (1≤t≤104) — the number of test cases.

Each test case consists of two lines.

The first line contains an integer n (1≤n≤2⋅105) — the length of the given sequence a.

The second line contains n integers a1,a2,…,an (1≤ai≤n) — elements of the given sequence a.

It is guaranteed that the sum of n values over all test cases does not exceed 2⋅105.

Output

For each test case print your answer on a separate line — the minimum number of elements that must be removed from the beginning of the sequence so that all remaining elements are different.

--------------------------------------------

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

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

他一举就能：

删除序列的第一个（最左边）元素。

例如，在一次移动中，序列 [3,1,4,3] 将产生序列 [1,4,3]，该序列由不同的数字组成。

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

输入

输入的第一行包含一个整数 t (1≤t≤104) — 测试用例的数量。

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

第一行包含一个整数 n (1≤n≤2⋅105) — 给定序列 a 的长度。

第二行包含 n 个整数 a1,a2,…,an (1≤ai≤n) — 给定序列 a 的元素。

保证所有测试用例的 n 值之和不超过 2⋅105。

输出

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

------------------------

倒叙，利用hashmap即可，下面是代码：