## ONEXLIS - One X LIS

no tags

For a given sequence a, a, ... 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:
254 3 3 4 155 4 3 2 1Output:
42 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. 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