B. Remove Prefix

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp was presented with some sequence of integers aa of length nn (1≤ai≤n1≤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][3,1,4,3] will produce the sequence [1,4,3][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 aa, after removing which all values in the sequence will be unique.

Input

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

Each test case consists of two lines.

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

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

It is guaranteed that the sum of nn values over all test cases does not exceed 2⋅1052⋅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.

Example

input

Copy

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

output

Copy

1
4
0
0
5

Note

The following are the sequences that will remain after the removal of prefixes:

• [1,4,3][1,4,3];
• [1][1];
• [1][1];
• [6,5,4,3,2,1][6,5,4,3,2,1];
• [2,1][2,1].

It is easy to see that all the remaining sequences contain only distinct elements. In each test case, the shortest matching prefix was removed.

解题说明：此题是确保数列中不同数字只出现一次，可以从末尾开始计算，找到第一次出现重复的，然后把该位置及其前面的全部删除即可。

#include
#include
 
int a[200001];
int t, n;
int main() 
{
	int i, flag;
	scanf("%d", &t);
	while (t--) 
	{
		flag = 0;
		int b[200001] = { 0 };
		scanf("%d", &n);
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
		}
		for (i = n; i > 0; i--)
		{
			if (b[a[i]] == 0)
			{
				b[a[i]] = 1;
			}
			else 
			{
				flag = i;
				break;
			}
		}
		printf("%d\n", flag);
	}
	return 0;
}