[Solution] Remove Prefix solution codeforces

Remove Prefix solution codeforces – Polycarp was presented with some sequence of integers 𝑎a of length 𝑛n (1𝑎𝑖𝑛1≤ai≤n). A sequence can make Polycarp happy only if it consists of different numbers (i.e. distinct numbers).

Table of Contents

[Solution] Remove Prefix solution codeforces

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 𝑎a, after removing which all values in the sequence will be unique.

[Solution] Remove Prefix solution codeforces

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

Each test case consists of two lines.

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

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛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 21052⋅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

[Solution] Remove Prefix solution codeforces

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.

 

For Solution

Click Here

Leave a Comment