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
2018-12-28 10:21:49 Ayush Vatsa
are the tags unique?
2018-07-07 17:18:41
anyone managed to submit AC in python?
2017-08-31 08:22:33
Here's how to submit 2 ACs within 5 sec -
1. Find questions like BORW and BAT2.
2. Write code for one.
3. Submit for both.
2017-06-17 18:54:06 Farhan
Please refrain from discussing the logic in the comments.
2017-02-11 17:46:36
AC in 1 go:-)
2017-01-25 13:13:27
Same as BORW.
2016-12-30 05:41:34
my 100th ^_^

Last edit: 2016-12-30 05:48:01
2016-10-27 23:27:22
Good problem for dp...AC in one go 0.00 sec :)
2016-08-21 12:05:11
@susi_45 In the given test case BATMAN goes this way 5 <- 3 <- 1 and Catwoman goes this way 4 -> 6 .
Easy if you get the concept. Do problem -> Black or White before this.
2016-05-08 22:04:33 Sushovan Sen
Can someone please explain the test case.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.