CF2144E2 Looking at Towers (difficult version)

This is the difficult version of the problem. The only differences between the easy and the difficult version are the constraints on $ t $ and $ n $ . Consider a row of $ m $ towers; the height of the $ i $ -th tower in the row is $ h_i $ . If you look at this row of towers from the left, you see all towers that are strictly higher than all towers before them. Similarly, if you look at this row of towers from the right, you see all towers that are strictly higher than all towers after them. For example, if the towers have heights $ [3, 5, 5, 7, 4, 6, 7, 2, 4] $ , then: - when looking from the left, you see towers with heights $ 3 $ , $ 5 $ and $ 7 $ ; - when looking from the right, you see towers with heights $ 7 $ and $ 4 $ . Let $ L(h) $ be the set of heights you see from the left, and $ R(h) $ be the set of heights you see from the right when the sequence of heights is $ h $ . In the example above, $ L(h) = \{3, 5, 7\} $ , and $ R(h) = \{4, 7\} $ . You are given a sequence $ a_1, a_2, \dots, a_n $ . Your task is to calculate the number of subsequences of $ a $ such that $ L(a) = L(a') $ and $ R(a) = R(a') $ , where $ a' $ is the subsequence you consider. Two subsequences are different if indices of chosen elements are different.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of two lines: - the first line contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ); - the second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ). Additional constraint on the input: the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, print one integer — the number of subsequences $ a' $ of the given sequence $ a $ such that $ L(a) = L(a') $ and $ R(a) = R(a') $ . Since it might be huge, print it modulo $ 998244353 $ .

In the first example, $ L(a) = \{4, 8\} $ , $ R(a) = \{3, 8\} $ . The subsequences included in the answer are: - $ [4, 8, 3] $ (the $ 1 $ -st, the $ 4 $ -th and the $ 5 $ -th element); - $ [4, 8, 3] $ (the $ 3 $ -rd, the $ 4 $ -th and the $ 5 $ -th element); - $ [4, 2, 8, 3] $ (the $ 1 $ -st, the $ 2 $ -nd, the $ 4 $ -th and the $ 5 $ -th element); - $ [4, 4, 8, 3] $ (the $ 1 $ -st, the $ 3 $ -rd, the $ 4 $ -th and the $ 5 $ -th element); - $ [4, 2, 4, 8, 3] $ (the whole sequence). In the second example, the only valid subsequence is the given sequence itself.