CF2075F Beautiful Sequence Returns

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.

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 $ .

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