CF2144E2 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$ 取模后的结果。

在第一个样例中，$L(a) = \{4, 8\}$，$R(a) = \{3, 8\}$。被计入答案的子序列有： - $[4, 8, 3]$（第 $1$、$4$、$5$ 个元素）； - $[4, 8, 3]$（第 $3$、$4$、$5$ 个元素）； - $[4, 2, 8, 3]$（第 $1$、$2$、$4$、$5$ 个元素）； - $[4, 4, 8, 3]$（第 $1$、$3$、$4$、$5$ 个元素）； - $[4, 2, 4, 8, 3]$（整段序列）。 在第二个样例中，唯一合法的子序列是整个序列本身。 由 ChatGPT 5 翻译