まず，\(A\) が決まっているときの \(f(A)\) の値について考えます．これは，「\(i < j\) に対して 無向辺 \((i, j)\) がある iff \(A_i = A_j\) かつ， \(A_k < A_i\) を満たす \(i < k < j\) がない 」ようなグラフを考えたときの連結成分の個数です．値が大きい方から連結成分ごとにその中の最小と最大を両端として操作すればよく，それより少ない操作回数では不可能です．証明の方針としては，値が大きい方から操作の必要性について考えると値の最大値についてはその回数必要で，先に操作をしておくとその値の部分を取り除いて考えることができます．

実際にはグラフの中で(区間として)極小な辺だけ考えればよく，左端でコスト \(1\), それ以外の頂点では左に辺があればコスト \(0\) として足せばよいです．

よって，全ての和としては \(N \times M^N\) から，コスト \(0\) の頂点の個数の和を引けばよいです．\((i, j)\) と \(A_i = x\) として固定するとこの組合せで \(j\) がコスト \(0\) となるのは \(\sum_{i=0}^{N-1} \sum_{j=0}^{i-1} (\sum_{x=1}^{M} (M - x) ^{i-j-1}) * M^{N-(i-j)-1}\) 通りです．これは \(i-j\) と \(x\) のみに依存するので \(\mathrm{O}(NM)\) で計算できます．

bonus : \(N\) や \(M\) をどれくらい大きくしても解けるでしょうか