BAT2 - BATMAN2

Alfred: "I'll get this to Mr. Fox, but no more. I've sewn you up, I've set your bones, but I won't bury you. I've buried enough members of the Wayne family."

After being promised the software to erase her criminal record, Catwoman agrees to take Batman to Bane. They manage to defeat all of Bane's men but ended up heading into a MAZE trap. Bane would call this maze as the LIS MAZE. He would hide himself in one of the rooms. Each of these rooms have a number (tag) associated with it. The speciality of the maze is that once you enter any room it will only lead you to rooms with a higher tag in the direction you move. Batman and Catwoman decide to move in opposite directions trying their luck to maximize the number of rooms they search. (They can start with any room, need not be the same)

Catwoman: "Never steal from someone you can't outrun, kid."

Input

t, number of testcases.
n, number of rooms.
n integers giving the tag associated with the rooms.

Output

The maximum number of rooms searched.

Constraints

1 ≤ n ≤ 100

Example

Input:
1
6
5 3 4 6 1 2

Output:
5

Added by:Romal Thoppilan
Date:2013-02-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2016-04-30 15:13:41 farhad chowdhury
really aww sum problem
cant wait to share the idea
simply go one way and give each number to a increasing or decreasing or nothing
max among three is ans
ac with 0.0

Last edit: 2016-04-30 15:14:57
2016-02-08 07:20:33 Liquid_Science
after 6 months ,AC IN 0.43,AC in 0.11, AC in 0.08 , Now fastest and only solution in JAVA :P
2016-02-03 12:34:54 sai krishna
What is the solution for 1 4 6 2 5 ?
(1 4 5),(2,6 ) or (1,4,6),(2)
2015-07-28 09:47:06 Bhuvnesh Jain
@Romal, can you check why is 1st solution is getting WA. I think my algo is correct. It gives 5 as output on test case as well
2015-07-28 09:47:04 Bhuvnesh Jain
@Romal, can you check why is 1st solution is getting WA. I think my algo is correct. It gives 5 as output on test case as well
2015-03-27 04:30:49 Micky
Can different rooms have same number(tag)???
2014-08-04 04:30:11 Rishav Goyal
A[i]<=100.

Last edit: 2014-08-04 04:30:23
2014-06-25 13:32:51 [themighty] deathsurgeon
What is the range of these n integers (i.e., tags)?

Last edit: 2014-07-21 15:59:59
2013-08-27 05:19:44 Hamdi Ahmadi Muzakkiy
anyone have testcase?
2013-07-30 11:47:09 Taym
The number of each room is positive, or could it be negative ?

Last edit: 2013-07-30 17:41:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.