先頭から値を決めていったとき、必要なのは \(1\) つ前の値のみですから、以下のような \(\mathrm{dp}\) を定義したときの \(\sum_{j=1}^M \mathrm{dp}_{N,j}\) が答えです。

\(\mathrm{dp}_{i,j} := b\) の先頭 \(i+1\) 項を条件を満たすように決めたときに \(b_{i+1}=j\) となる場合の数

条件が \(\max\) と \(\min\) であり、大小関係のみに着目していることより、\(A_i\) との大小関係が等しい整数 \(j,k\) について、 \(\mathrm{dp}_{i,j}=\mathrm{dp}_{i,k}\) であることがわかります。大小関係が同じものを同一視して \(\mathrm{dp}\) の遷移を行うことで、一度の遷移を \(O(1)\) で行うことができます。

よって、この問題を時間計算量 \(O(N)\) で解くことができました。遷移の時に適切な係数をかける必要があることに気を付けて下さい。

実装例 (C++)