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 builing 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 Specification:
First line contains an integer T( 1 < = T < = 100) that represents the number of test cases.Then follows the T containg 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 Specification:
For each test case, print only one line, the maximum length of such sequence.
Sample input:
2
10
1 3 5 6 4 8 4 3 2 1
6
8 6 3 4 2 1
Sample Output:
9
5
Explanation
for first test case the subsequence is : 1 3 5 6 8 4 3 2 1 for second case it is : 8 6 4 2 1
hide comments
ab_biswas09:
20190318 16:43:29
Very easy problem 

zakir068:
20190223 17:23:45
nice problem.just modify the classic lis


sudhanshu6324:
20181114 18:46:08
@mudra03 try 4 4 ans should be 1 

castor21:
20180617 07:25:08
AC not working in my house. 

harvy98:
20180525 18:58:41
Nice variation of LIS. 

burninggoku:
20170925 09:05:31
longest bitonic subsequence.. :) 

mudra03:
20170924 17:49:34
getting WA ANY Tricky cases?


deadpool_18:
20170601 13:04:37
easy one! Last edit: 20170601 13:18:56 

omprakash_40:
20170420 09:30:39
easy one . Simple Dynamic Programming problem.


vengatesh15:
20170127 12:24:45
did using O(nlogn) algo AC in 1 go 
Added by:  Rajesh Kumar 
Date:  20130901 
Time limit:  0.216s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  AASF  ABVIIITM PC0192013 