Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hexo The Tree Planter

Limits: 1s, 512 MB

Hexo has a large field. The field can be modeled as a 1 x N grid. Some parts of the field have trees with various species, some are empty. Each species have a code of 32 bit signed integer. The empty spaces are denoted as 0 (zero).

Hexo can plant some trees on those empty spaces if he wishes. Now he wants to fill up those empty spaces in a way so that he can get a long contiguous segment with same species tree. Can you help Hexo to find out the length of the longest contiguous segment from his land consists of tree from same species ? Note that, Hexo will plant those trees in a optimal way.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases. Each case starts with a line containing an integer N (0 < N < 100001). The next line contains N integers, each one will fit in 32 bit signed integer.

Output

For each case, output the case number first followed by the length of the longest contiguous sub-segment Hexo can have with same species tree. For details follow sample input and output.

Samples

InputOutput
3
2
2 0
3
1 1 2
5
1 3 0 3 1
Case 1: 2
Case 2: 2
Case 3: 3

For the first case, Hexo can plant a tree from species 2 in the empty spot. Then he gets maximum length of 2.

For the second case, there is no empty slots. So, he doesn’t need to plant any tree and gets maximum length of 2 from the first two spots.

For the third case, Hexo will plant tree with species 3 in the empty spot.

Data set is huge, use Faster IO

Author
  • faiyaz26's Avatar

    faiyaz26

    Faiyaz refers to himself as a lazy software engineer. He likes coffee, sleep and solving problems. He qualified to ACM-ICPC World Finals 2016 from North South University and secured top ranks in numerous national contests.
Discussion
Submit

Login to submit