The Lucky Draw

Problem code: D2

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 a1, a2, ..., an 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; ai 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 ≤ 106).

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
Date Added: 5-05-2009
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, C, C99 strict, CPP 4.0.0-8, CS2, D, FORT, JAR, JAVA, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PYTH, PYTH 3.1.2, RUBY, SCALA, ST


Comments

I think, accepted solutions

uniquecode @ 15 Dec 2009 10:38 PM

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

ankit1990 @ 17 May 2010 09:22 PM

@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

gopi6sigma @ 14 Sep 2010 06:14 PM

Perhaps, it should have been told non-decreasing order rather than increasing order ... is nt it ??

sorry .. did nt read it

gopi6sigma @ 14 Sep 2010 06:31 PM

sorry .. did nt read it properly ... its strictly increasing

Why cant i submit answer in

gunjanbansal @ 10 Oct 2010 01:07 PM

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 :(

gunjanbansal @ 10 Oct 2010 01:14 PM

sorry its g++ 4.3.2 :(

hints please me to stuck with

gunjanbansal @ 10 Oct 2010 02:39 PM

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_i_k_h_i_l @ 22 May 2012 07:50 PM
Even an NlogN solution in java gives a TLE.

n^2 log(n) giving TLE... i

ankitsaha @ 17 Oct 2012 08:46 PM
n^2 log(n) giving TLE... i think codechef should increase the base time limit.......

Make sure you have used scanf

saifhhasan @ 31 Oct 2012 05:43 PM
Make sure you have used scanf printf (Fast IO) if your submitted in C++. Your reading lots number so it matters much. I don't think N^2 * log(N) will work because there are 15 testcases to handle. There must be some use of randomness.

can someone help me where i m

phodu17 @ 19 Dec 2012 05:31 PM
can someone help me where i m going wrong . i am not getting it. http://www.codechef.com/viewsolution/1637126

@uniquecode your test answer

itisnesa @ 27 Mar 2013 11:40 PM
@uniquecode your test answer is wrong . the correct answer is 105 since (starting 52 ...... ending 157 )

SUCCESSFUL SUBMISSIONS


Fetching successful submissions

HELP




 





Program should read from standard input and write to standard output.  After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:


 


    
    
  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.

    • 
    
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.

    • 
    
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.

    • 
    
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.

    • 
    
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • 
    If you are still having problems, see a sample solution here.