A16645 | Looking at Towers (difficult version)

这是本题的困难版本。简单版本与困难版本的唯一区别在于 $t$ 和 $n$ 的数据范围。

现有一排 $m$ 个塔，第 $i$ 个塔的高度为 $h_i$。

如果你从左边看这排塔，则会看到所有比前面所有塔都高的塔。同样地，如果你从右边看这排塔，则会看到所有比后面所有塔都高的塔。例如，如果这排塔的高度为 $[3, 5, 5, 7, 4, 6, 7, 2, 4]$，那么：

- 从左边看，可以看到高度为 $3$、$5$ 和 $7$ 的塔；
- 从右边看，可以看到高度为 $7$ 和 $4$ 的塔。

记 $L(h)$ 为从左边看到的高度集合，$R(h)$ 为从右边看到的高度集合，其中 $h$ 是当前的高度序列。以上述例子为例：$L(h) = \{3, 5, 7\}$，$R(h) = \{4, 7\}$。

你有一个序列 $a_1, a_2, \dots, a_n$。你的任务是计算有多少个 $a$ 的子序列 $a'$ 满足 $L(a) = L(a')$ 且 $R(a) = R(a')$，其中 $a'$ 是你考虑的子序列。只要选择的元素下标不同，子序列就被认为是不同的。

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每组测试包括两行：

- 第一行一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）；
- 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）。

输入还保证：所有测试的数据中，$n$ 的总和不超过 $3 \cdot 10^5$。

对于每组测试，输出一个整数，表示满足条件的子序列数量。由于答案可能很大，请输出对 $998244353$ 取模后的结果。