CODERE3 - Coder Express 3!!

Mr Durgeshwara was very impressed by Rahul. But now he was in trouble. He has already fixed his daughter's marriage with Thangabali who was the best coder of his town. He got an idea and arranged a contest between Rahul and Thangabali. They have to solve a problem at the same time and whoever solves first will marry Meenamma. Rahul was not such a good coder and was also getting help from Meenamma. Your task is to help Thangabali to solve the problem to create a twist in story.

The problem was that there are large number of building in the town which are of different heights and all the building are in a single line.

You have to find the maximum possible length of the subsequences of buildings which are possible which are first increasing in heights and then decreasing! Please Note: the heights of the building in the subsequences should be strictly increasing and then strictly decreasing.

Input

First line contains an integer T (1 ≤ T ≤ 100) that represents the number of test cases. Then follows the T containing the integer N (1 ≤ N ≤ 1000) specifying the total number of elements and the next line contains the N integers A1, A2, A3 ... An (1 ≤ Ai ≤ 1000)

Output

For each test case, print only one line, the maximum length of such sequence.

Example

Input:
2
10
1 3 5 6 4 8 4 3 2 1
6
8 6 3 4 2 1

Output:
9
5

Explanation

For the first test case the subsequence is : 1 3 5 6 8 4 3 2 1. For the second test case it is : 8 6 4 2 1


Added by:Rajesh Kumar
Date:2013-09-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:AASF - ABV-IIITM PC-01-9-2013

hide comments
2016-08-19 14:52:49
nothing new still time limit that bad for python/java.
atleast in such problems keep TL fair for all languages.
2016-08-08 21:07:20
Candid! :)
2016-08-07 21:02:36
easy
2016-07-28 17:50:02 Purav Shah
My 300th!!! :D
2016-07-20 18:34:43
AC in one go 0.10.......longest bitonic subsequence;)

Last edit: 2016-07-21 06:05:37
2016-07-08 12:57:04
Somehow my O(2 * N^2) solution is faster than my O(2 *N + N^2) solution. o.O :D
2016-06-26 08:57:19
longest bitonic subsequence...ac in 1 go
2016-04-23 18:39:05
thanks @Rishit!!!!
2016-04-19 10:16:05
Easy
2015-08-16 17:28:59 Liquid_Science
Too tough in java :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.