はじめに生成されるグラフの特徴を観察しましょう．

実験などを行うと，連結成分は数列の区間と対応していることがわかります．つまり，頂点 \(i\) と頂点 \(i+k\) が連結な場合，頂点 \(i\) と頂点 \(i+1,\ldots,i+k-1\) も連結になっています．

更に，頂点 \(i\) と頂点 \(i+1\) が連結にならない必要十分条件が，\(\min(A_1,\ldots,A_i )> \max(A_{i+1}, \ldots, A_N)\) であることも分かります．

これは \(N\) に関する数学的帰納法により証明できます．

この事実より，連結成分数は \(1+ \) (頂点 \(i\) と頂点 \(i+1\) が連結でないような頂点 \(i \ (1\leq i \leq N-1)\) の個数) として求めることができます．

主客転倒を用いると，頂点 \(i\) と頂点 \(i+1\) が連結でないような数列の個数を各 \(i\) について求められれば良いです．

連結にならない必要十分条件の左辺，つまり \(\min(A_1,\ldots,A_i )\) の値を全探索すれば，頂点 \(i\) と頂点 \(i+1\) が連結でない数列の個数を \(\mathrm{O}(M)\) で求められます．

以上よりこの問題を \(\mathrm{O}(NM)\) で解くことができました．

Bonus: \(N\leq 2000, M< 998244353\) でも解けます．