ONEXLIS  One X LIS
For a given sequence a[1], a[2], ... a[n], lets call a subsequence a[k_{1}], ...a[k_{i}]... a[k_{m}] (where 1<=k_{i}<=n and k_{i}<k_{i+1}) as "one X increasing subsequence" if there is exactly one i between 1 and m1 (inclusive) for which a[k_{i}]>a[k_{i+1}]. Given a sequence find the length of the longest "one X increasing subsequence".
Input
First line contains t, which denotes the number of test cases. 2*T lines follow. Each test case is described using 2 lines.
First line of a test case contains an integer n, which denotes the number of elements in the array.
Second lines contains n integers, which represent a[i] 1<=i<=n.
1<=t<=20
1<=n<=100000
1<=a[i]<=10^9
Output
For each test case, print one integer which represents the number of integers in the One X LIS. The output for each test case should be printed on a new line.
Example
Input: 2
5
4 3 3 4 1
5
5 4 3 2 1
Output: 4
2
Explanation:
In the first test case, the Longest Increasing Subsequence is 3.3.4 whereas the longest One X Subsequence is 4.3.3.4 whose length is 4.
In the second example, any two elements can be chosen to form the longest One X Subsequence, which gives us an answer of 2.
hide comments
sxie12:
20220911 23:05:06
Input is fine. The one x increasing subsequence MUST have a k where a[k] > a[k + 1]. Therefore the output to 1 2 3 4 5 is 0 because no subsequence of that sequence satisfies the condition. 

Luka:
20140102 14:36:35
getting WA. Please check @problem setter. I hope the inputs are fine. 

Amit Jain:
20140101 15:13:05
what should be output for 1 2 3 4 5???


Miso Forisek:
20131227 12:07:34
At the moment, the statement is incomplete / incorrect. In some test cases the input is a nondecreasing sequence, and the statement does not define the correct return value in such a case. Apparently, the author expects you to output 0 for such test cases. 

Siwakorn Srisakaokul:
20131029 01:40:07

Added by:  TouristGuide 
Date:  20130203 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Bytecode 2013 