ONEXLIS - One X LIS

For a given sequence a[1], a[2], ... a[n], lets call a subsequence a[k1] ...a[ki]... a[km] (where 1 <= ki <= n and kii+1) as "one X increasing subsequence" if there is exactly one i between 1 and m-1 (inclusive) for which a[ki]>a[ki+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.


Added by:TouristGuide
Date:2013-02-03
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2013

hide comments
2022-09-11 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.
2014-01-02 14:36:35 Luka
getting WA. Please check @problem setter. I hope the inputs are fine.
2014-01-01 15:13:05 Amit Jain
what should be output for 1 2 3 4 5???
0 or 5?
2013-12-27 12:07:34 Miso Forisek
At the moment, the statement is incomplete / incorrect. In some test cases the input is a non-decreasing 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.
2013-10-29 01:40:07 Siwakorn Srisakaokul
It should be more specific that the x increasing subsequence needs to have length > 1.

This follows from "if there is exactly one i".

[edited by misof]

Last edit: 2013-12-27 12:04:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.