Unique Snowflakes

Interview

Time limit1sMemory limit128 MB

Summary

Given a stream of integer snowflake ids, find the length of the longest contiguous block in which every value is distinct.

Level: Medium4 of 10
Topics: Sliding window, Hash map, Array, Two pointers
Solved: No attempts yet

Problem

Emily has a business idea: packaging and selling snowflakes. Her machine catches falling snowflakes and serializes them into a single stream that flows, one at a time, into a package. Once a package is full it is sealed and shipped.

The company's motto is bags of uniqueness: every snowflake in a package must differ from all of the others. This is hard, because many of the snowflakes coming through the machine are identical. Emily wants to know the size of the largest possible package of unique snowflakes.

The machine may begin filling a package at any moment, but once it starts, every snowflake that flows out must go into the package until it is completed and sealed. In other words, a package is a contiguous block of the stream, and you must find the length of the longest contiguous block in which all snowflakes are distinct.

Input

The first line contains an integer $T$ , the number of test cases. Each test case begins with a line containing an integer $n$ , the number of snowflakes processed by the machine. The next $n$ lines each contain one integer in the range $0$ to $10^9$ inclusive, identifying a snowflake; two snowflakes have the same integer if and only if they are identical. The total number of snowflakes over all test cases is at most $10^6$ .

Output

For each test case, output a single line containing one integer: the maximum number of snowflakes that can be in a package, i.e. the length of the longest contiguous block of the stream in which every snowflake is distinct.

Examples3

Example 1
Input
```
1
5
1
2
3
2
1
```
Expected output
```
3
```
Example 2
Input
```
1
6
1
2
3
4
5
6
```
Expected output
```
6
```
Example 3
Input
```
1
5
7
7
7
7
7
```
Expected output
```
1
```