Garland Of Roses

Time Limit: 1 sec

 

The Problem

Diya loves roses. She has a garden with beautiful roses . She likes to make garlands of roses. She prefers to put the roses in decreasing order of weight, with the heaviest rose at the front of the string of the garland. Unfortunately, sorting roses  is not easy. she cannot simply pick up a rose and place it somewhere else. It is impractical to insert a rose within an existing garland of roses. A rose may only be added to the beginning and end of the string. roses are kept in a predetermined order. When each rose she picks, Diya can add it to the beginning or end of her string of garland, or refuse to add it at all. The resulting garland should be as long as possible, but the roses within it must be ordered by weight. Given the weights of the roses in the order in which they are taken from the garden, what is the longest garland that Diya can make?

 

The Input

The first line is the number of test cases to follow. The test cases follow, one after another; the format of each test case is the following: The first line contains an integer 0 ≤ n ≤ 2000, the number of roses. Each of the following n lines contains a non-negative integer Pi (<=50000) giving the weight of the roses. No two roses have the same weight.

 

The Output

Output a single integer giving the number of roses in the longest garland that can be made with the given restrictions.

 

Sample Input

2

3

1

2

3

4

1

2

3

4

 

Sample Output

3

4

 

 

 

[Outsbook Round #2 Online Contest]

Problem Setter: Parag Paul