这是问题F的第二个子任务。它与第一个子任务之间的唯一区别是$$$m$$$的值的约束和时间限制。解决这个子任务就足以破解它,但是您需要解决两个子任务才能破解第一个子任务。
宇宙中有 $$$n+1$$$ 种不同的颜色,编号为 $$$0$$$ 到 $$$n$$$。有一条 $$$m$$$ 厘米长的纸条,最初涂有颜色 $$$0$$$。
Alice 拿起画笔并按照以下过程绘制了条带。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,按此顺序,她选择两个整数 $$$0 \leq a_i < b_i \leq m$$$,使得段 $$$[a_i, b_i]$$$ 当前使用单一颜色绘制,并用颜色 $$$i$$$ 重新绘制它。
Alice 选择这些片段的方式是,现在每一厘米都涂上 $$$0$$$ 以外的某种颜色。形式上,线段 $$$[i-1, i]$$$ 用颜色 $$$c_i$$$ ($$$c_i \neq 0$$$) 绘制。除了 $$$0$$$ 之外的所有颜色都在条上可见。
计算导致此配置的不同序列对 $$$\{a_i\}_{i=1}^n$$$、$$$\{b_i\}_{i=1}^n$$$ 的数量。
由于这个数字可能很大,因此输出它对 $$$998244353$$$ 取模。
输入
第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 500$$$, $$$n \leq m \leq 10^6$$$) - 分别是不包括颜色 $$$0$$$ 的颜色数和纸张长度。
第二行包含 $$$m$$$ 空格分隔的整数 $$$c_1, c_2, \ldots, c_m$$$ ($$$1 \leq c_i \leq n$$$) — 进程结束后 $$$[i-1, i]$$$ 段上可见的颜色。保证对于 $$$1$$$ 和 $$$n$$$ 之间的所有 $$$j$$$,存在一个索引 $$$k$$$,使得 $$$c_k = j$$$。
输出
输出一个整数 - Alice 可以执行绘画的方式数,以 $$$998244353$$$ 为模。
示例
输入 #1
3 3 1 2 3
输出 #1
5
输入 #2
2 3 1 2 1
输出 #2
1
输入 #3
2 3 2 1 2
输出 #3
0
输入#4
7 7 4 5 1 6 2 3 7
输出#4
165
输入 #5
8 17 1 3 2 2 7 8 2 5 5 4 4 4 1 1 6 1 1
输出 #5
20
注意
在第一个示例中,有 $$$5$$$ 种方式,全部如下图所示。这里,$$$0$$$ 是白色,$$$1$$$ 是红色,$$$2$$$ 是绿色,$$$3$$$ 是蓝色。
下面是无效绘制过程的示例,因为在第二步中,段 1 3 不是单色,因此不能用颜色 $$$2$$$ 重新绘制。
在第二个示例中,Alice 必须首先使用颜色 $$$1$$$ 绘制段 0 3,然后使用颜色 $$$2$$$ 绘制段 1 2。