Alan Turing is standing on a tape divided into cells that is infinite in both directions.
Cells are numbered with consecutive integers from left to right. Alan is initially standing in cell. Every cell has cell on the left and cell on the right.
Each cell can either contain an integer or be empty. Initially all cells are empty.
Alan is given a permutation uniformly at random among all permutations of length .of integers from to that was chosen
At time, integer is written down into cell where Alan is located.
At each timefrom to inclusive, the following happens. First, Alan decides whether to stay in the same cell he’s currently in, move to the neighboring cell on the left, or move to the neighboring cell on the right. After that, integer is written down into the cell where Alan is located. If that cell already contained some integer, the old integer is overwritten and irrelevant from that moment on.
Onceis written down into some cell at time , sequence of all integers contained in the cells from left to right is formed. Empty cells are ignored.
Turing’s award is equal to the length of the longest increasing subsequence of sequence.
Help Alan and determine the largest possible value of his award if he acts optimally.
Each test contains multiple test cases. The first line contains the number of test cases( ). Description of the test cases follows.
Each test case is given in two lines. The first line of each test case contains a single integer( ) — the length of the permutation given to Alan.
The second line containsdistinct integers ( ) — the elements of the permutation.
It is guaranteed that the permutation was chosen uniformly at random among all permutations of the corresponding length.
The sum ofover all test cases does not exceed .
For each test case output a single integer — the largest possible value of Turing’s award.
Hacks are not allowed for this problem.
4 2 1 2 4 4 1 2 3 7 3 6 5 7 4 1 2 7 5 2 3 7 6 1 4
2 3 4 4
Longest increasing subsequence of sequence is the longest increasing sequence that can be obtained from by deletion of several (possibly, zero or all) elements.
In the first test case, Alan can make a decision only at time. If Alan stays in cell , sequence will be equal to . If Alan moves to the left, to cell , sequence will be equal to . If Alan moves to the right, to cell , sequence will be equal to . Only in the last case the length of the longest increasing subsequence of is , therefore, the answer is equal to .
In the second test case, one of the optimal sequences of actions looks as follows: move to the left at timesand , and move to the right at time . Then sequence will be equal to , and the length of its longest increasing subsequence is .
In the third test case, one of the best ways is to always move to the left. Then sequencewill be equal to , and the length of its longest increasing subsequence is .
In the fourth test case, one of the best ways is to move to the right four times, then move to the left once, and stay in the same cell once. Sequencewill be equal to .
Also read : Wafa Na Raas Aayi Lyrics