F. Beautiful Sequence Returns
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's call an integer sequence beautiful if the following conditions hold:

  • for every element except the first one, there is an element to the left less than it;
  • for every element except the last one, there is an element to the right larger than it;

For example, $$$[1, 2]$$$, $$$[42]$$$, $$$[1, 4, 2, 4, 7]$$$, and $$$[1, 2, 4, 8]$$$ are beautiful, but $$$[2, 2, 4]$$$ and $$$[1, 3, 5, 3]$$$ are not.

Recall that a subsequence is a sequence that can be obtained from another sequence by removing some elements (possibly zero) without changing the order of the remaining elements.

You are given an integer array $$$a$$$ of size $$$n$$$. Find the longest beautiful subsequence of the array $$$a$$$ and print its length.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Next, $$$t$$$ independent cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) – the array $$$a$$$.

Additional constraint on the input: the total sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print one integer — the length of the longest beautiful subsequence of array $$$a$$$.

Example
Input
5
1
42
5
1 2 3 4 5
6
6 5 4 3 2 1
7
1 1 3 4 2 3 4
6
2 3 1 1 2 4
Output
1
5
1
5
3