F. Beautiful Sequence Returnstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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.InputThe 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$$$.OutputFor each test case, print one integer — the length of the longest beautiful subsequence of array $$$a$$$.ExampleInput514251 2 3 4 566 5 4 3 2 171 1 3 4 2 3 462 3 1 1 2 4Output1 5 1 5 3