The Lucky Draw

All submissions for this problem are available.
The Chef is planning a buffet for the DirectiPlex inauguration party, and everyone is invited. On their way in, each guest picks up a sheet of paper containing a random number (this number may be repeated). The guests then sit down on a round table with their friends.
The Chef now decides that he would like to play a game. He asks you to pick a random person from your table and have them read their number out loud. Then, moving clockwise around the table, each person will read out their number. The goal is to find that set of numbers which forms an increasing subsequence. All people owning these numbers will be eligible for a lucky draw! One of the software developers is very excited about this prospect, and wants to maximize the number of people who are eligible for the lucky draw. So, he decides to write a program that decides who should read their number first so as to maximize the number of people that are eligible for the lucky draw. Can you beat him to it?
Input
The first line contains t, the number of test cases (about 15). Then t test cases follow. Each test case consists of two lines:
 The first line contains a number N, the number of guests invited to the party.
 The second line contains N numbers a_{1}, a_{2}, ..., a_{n} separated by spaces, which are the numbers written on the sheets of paper in clockwise order.
Output
For each test case, print a line containing a single number which is the maximum number of guests that can be eligible for participating the the lucky draw.
Constraints
 1 ≤ N ≤ 10000
 You may assume that each number number on the sheet of paper; a_{i} is randomly generated, i.e. can be with equal probability any number from an interval [0,U], where U is some upper bound (1 ≤ U ≤ 10^{6}).
Example
Input: 3 2 0 0 3 3 2 1 6 4 8 6 1 5 2 Output: 1 2 4
Output details
Case 1: No matter where who reads there number first, just one person is eligible for the lucky draw.
Case 2: The person in the last position could read their number first to obtain the sequence 1 3 2. We could then pick 2 sheets with numbers 1 and 2.
Case 3: The person in the fourth position could read their number first to obtain the sequence 1 5 2 4 8 6. We could then pick 4 sheets with numbers 1 2 4 6.
Author:  admin 
Tags  admin 
Date Added:  5052009 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, C, C99 strict, CPP 4.9.2, CPP14, CS2, D, FORT, GO, JAVA, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PYTH, PYTH 3.4, RUBY, SCALA, ST 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
I think, accepted solutions
I think, accepted solutions are wrong...
Test case:
1
157
54 55 56....105 1 2 3 4.....51 106 107 108.....157 52 53
the answer should be 103.
The accepted solutions are wrong. Admin please check!!
@All Hi , I assume that
@All
Hi , I assume that almost all u guys have calculated N longest increasing subsequences each in order NlogN , which makes ur algorithm complexity in N^2 logN. Am i correct ? Can anyone suggest a better solution ?
Perhaps, it should have been
Perhaps, it should have been told nondecreasing order rather than increasing order ... is nt it ??
sorry .. did nt read it
sorry .. did nt read it properly ... its strictly increasing
Why cant i submit answer in
Why cant i submit answer in gcc 4.3.2 ?? Giving me errors that u cannot submit answer is this language.
sorry its g++ 4.3.2 :(
sorry its g++ 4.3.2 :(
hints please me to stuck with
hints please me to stuck with n^2 log(n) solution which is giving me TLE. I dont want to see soltuions, just need guidance in right direction.
Even an NlogN solution in
n^2 log(n) giving TLE... i
Make sure you have used scanf
can someone help me where i m
@uniquecode your test answer
TLE for n^^2 logn solution in