Time Limit: 1s
Memory Limit: 65535k
In Linear algebra, we have learned the definition of inversion number:
Assuming A is a ordered set with n numbers ( n > 1 ) which are different from each
other. If exist positive integers i , j, ( 1 ≤ i ＜ j ≤ n and A[i] ＞ A[j]), <A[i], A[j]> is
regarded as one of A’s inversions. The number of inversions is regarded as inversion
number. Such as, inversions of array <2,3,8,6,1> are <2,1>, <3,1>, <8,1>, <8,6>,
<6,1>,and the inversion number is 5.
Similarly, we define a new notion —— sequence number, If exist positive integers i, j, ( 1
≤ i ≤ j ≤ n and A[i] <= A[j], <A[i], A[j]> is regarded as one of A’s sequence pair. The
number of sequence pairs is regarded as sequence number. Define j – i as the length of the
Now, we wonder that the largest length S of all sequence pairs for a given array A.
There are multiply test cases.
In each case, the first line is a number N(1<=N<=50000 ), indicates the size of the array,
the 2th ~n+1th line are one number per line, indicates the element Ai （1<=Ai<=10^9） of
Output the answer S in one line for each case.