ONEXLIS - One X LIS

no tags 

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 ki<ki+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.


hide comments
sxie12: 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.

Luka: 2014-01-02 14:36:35

getting WA. Please check @problem setter. I hope the inputs are fine.

Amit Jain: 2014-01-01 15:13:05

what should be output for 1 2 3 4 5???
0 or 5?

Miso Forisek: 2013-12-27 12:07:34

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.

Siwakorn Srisakaokul: 2013-10-29 01:40:07

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

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