Long Colorful Strip

### 题目描述 这是 F 题的第二个子任务。F1 和 F2 的区别仅在对于 $m$ 和时间的限制上 有 $n+1$ 种颜色标号从 $0$ 到 $n$，我们有一条全部染成颜色 $0$ 的长为 $m$ 的纸带。 Alice 拿着刷子通过以下的过程来给纸带染色： 我们按照从 $1$ 到 $n$ 的顺序进行染色，进行每次染色时，我们选取一个区间 $[a_i,b_i]$，$0 \le a_i < b_i \le m$，并且这个区间内必定是单种颜色。 染色到最后，纸带上有各种颜色除了颜色 $0$。给出纸带最终的状态，问有多少种不同的染色方案能到达最终状态。输出时结果模 $998244353$。 ### 输入格式 第一行有两个整数 $n$ 和 $m$，$1 \le n \le 500$，$n \le m \le 10^6$。$n$ 代表除了颜色 $0$ 有多少种颜色，$m$ 代表纸带的长度。 第二行有 $m$ 个用空格分隔的整数 $c_1,c_2,\dots,c_m$，$1<=c_i<=n$，代表完成染色后纸带的最终状态。保证最终状态中能在纸带上找到从 $1$ 到 $n$ 所有的颜色。 ### 输出格式 输入一个单独的整数，即 Alice 可行的染色方案数模 $998244353$。

This is the second subtask of problem F. The only differences between this and the first subtask are the constraints on the value of $ m $ and the time limit. It is sufficient to solve this subtask in order to hack it, but you need to solve both subtasks in order to hack the first one. There are $ n+1 $ distinct colours in the universe, numbered $ 0 $ through $ n $ . There is a strip of paper $ m $ centimetres long initially painted with colour $ 0 $ . Alice took a brush and painted the strip using the following process. For each $ i $ from $ 1 $ to $ n $ , in this order, she picks two integers $ 0 \leq a_i < b_i \leq m $ , such that the segment $ [a_i, b_i] $ is currently painted with a single colour, and repaints it with colour $ i $ . Alice chose the segments in such a way that each centimetre is now painted in some colour other than $ 0 $ . Formally, the segment $ [i-1, i] $ is painted with colour $ c_i $ ( $ c_i \neq 0 $ ). Every colour other than $ 0 $ is visible on the strip. Count the number of different pairs of sequences $ \{a_i\}_{i=1}^n $ , $ \{b_i\}_{i=1}^n $ that result in this configuration. Since this number may be large, output it modulo $ 998244353 $ .

The first line contains a two integers $ n $ , $ m $ ( $ 1 \leq n \leq 500 $ , $ n \leq m \leq 10^6 $ ) — the number of colours excluding the colour $ 0 $ and the length of the paper, respectively. The second line contains $ m $ space separated integers $ c_1, c_2, \ldots, c_m $ ( $ 1 \leq c_i \leq n $ ) — the colour visible on the segment $ [i-1, i] $ after the process ends. It is guaranteed that for all $ j $ between $ 1 $ and $ n $ there is an index $ k $ such that $ c_k = j $ .

Output a single integer — the number of ways Alice can perform the painting, modulo $ 998244353 $ .

3 3
1 2 3

5

2 3
1 2 1

1

2 3
2 1 2

0

7 7
4 5 1 6 2 3 7

165

8 17
1 3 2 2 7 8 2 5 5 4 4 4 1 1 6 1 1

20

In the first example, there are $ 5 $ ways, all depicted in the figure below. Here, $ 0 $ is white, $ 1 $ is red, $ 2 $ is green and $ 3 $ is blue.  Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour $ 2 $ .  In the second example, Alice must first paint segment 0 3 with colour $ 1 $ and then segment 1 2 with colour $ 2 $ .