← 返回题目列表

Codeforces · 2144/E2

E2. 看塔(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。简单版本和困难版本之间的唯一区别是对 $$$t$$$ 和 $$$n$$$ 的约束。

考虑一排 $$$m$$$ 塔;该行中第 $$$i$$$ 塔的高度为 $$$h_i$$$。

如果你从左边看这排塔,你会看到所有塔都严格高于它们之前的所有塔。同样,如果您从右侧查看这一排塔楼,您会看到所有塔楼都严格高于其之后的所有塔楼。例如,如果塔的高度为 $$$[3, 5, 5, 7, 4, 6, 7, 2, 4]$$$,则:

  • 从左侧看,您会看到高度为 $$$3$$$、$$$5$$$ 和 $$$7$$$ 的塔楼;
  • 从右侧看时,您会看到高度为 $$$7$$$ 和 $$$4$$$ 的塔。

当高度序列为 $$$h$$$ 时,设 $$$L(h)$$$ 为从左侧看到的高度集合,$$$R(h)$$$ 为从右侧看到的高度集合。在上面的示例中,$$$L(h) = \{3, 5, 7\}$$$,$$$R(h) = \{4, 7\}$$$。

给定一个序列 $$$a_1, a_2, \dots, a_n$$$。您的任务是计算 $$$a$$$ 的子序列数,使得 $$$L(a) = L(a')$$$ 且 $$$R(a) = R(a')$$$,其中 $$$a'$$$ 是您考虑的子序列。如果所选元素的索引不同,则两个子序列不同。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 — 给定序列 $$$a$$$ 的子序列 $$$a'$$$ 的数量,使得 $$$L(a) = L(a')$$$ 且 $$$R(a) = R(a')$$$。因为它可能很大,所以打印它对 $$$998244353$$$ 取模。

示例

输入
复制

5
5
4 2 4 8 3
5
1 2 3 2 1
6
1 2 3 3 2 1
9
3 5 5 7 4 6 7 2 4
1
10

输出
复制

5
1
3
51
1

注意

在第一个示例中,$$$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$$$-st、$$$3$$$-rd、第 $$$4$$$ 和第 $$$5$$$-th 元素);
  • $$$[4, 2, 4, 8, 3]$$$(整个序列)。

在第二个示例中,唯一有效的子序列是给定序列本身。