Defense Line

Time limit3sMemory limit128 MB

Summary

Given an array, find the maximum length of a strictly increasing run achievable after deleting a single contiguous segment (possibly empty).

Level: Medium6 of 10
Topics: Array, Two pointers, Greedy
Solved: No attempts yet

Problem

The war that made the whole country suffer is over. Learning from it, it is time to strengthen the defense line of Ardenia's capital. The most critical part of the line is the row of mage towers stretching from the capital into the northern forest. The mages who guard it gave you, the king, one piece of advice about defense. In short, the quality of the city's defense is determined by the length of the longest run of consecutive towers whose heights are in strictly increasing order.

Building new towers is impossible, so for now you want to improve the defense by removing some towers (you may remove none). Because removing towers is tricky, the mages imposed one condition: the towers you remove must be consecutive.

For example, suppose the tower heights are 5, 3, 4, 9, 2, 8, 6, 7, 1. If you remove the consecutive segment 9, 2, 8, the remaining heights are 5, 3, 4, 6, 7, 1, and the longest consecutive increasing run is 3, 4, 6, 7 with length 4.

Input

The input consists of several test cases.

The first line contains the number of test cases $Z$ ( $Z \le 25$ ).

Each test case consists of two lines. The first line contains a positive integer $n$ ( $n \le 2 \cdot 10^5$ ), the number of towers. The second line contains $n$ positive integers not exceeding $10^9$ , separated by spaces, giving the heights of the towers.

Output

For each test case, print on its own line the length of the longest consecutive strictly increasing run of towers that can be obtained by removing some number (possibly zero) of consecutive towers.

Examples6

Example 1

Input

2
9
5 3 4 9 2 8 6 7 1
7
1 2 3 10 4 5 6

Expected output

4
6

Example 2
Input
```
1
1
7
```
Expected output
```
1
```
Example 3
Input
```
1
6
1 2 3 4 5 6
```
Expected output
```
6
```
Example 4
Input
```
1
5
5 4 3 2 1
```
Expected output
```
1
```
Example 5
Input
```
1
9
1 2 3 4 100 5 6 7 8
```
Expected output
```
8
```
Example 6
Input
```
1
6
3 3 3 3 3 3
```
Expected output
```
1
```