First, let us consider the value \(f(A)\) for fixed \(A\). This is the number of connected component in a graph where there is an undirected edge between vertices \(i < j\) iff \(A_i = A_j\) and there is no \(i < k < j\) such that \(A_k < A_i\). We can achieve it by dealing with the connected components in the descending order of the value and using the vertices with the smallest and largest indices as the endpoints in the operation. We cannot meet the objective with fewer operations. The proof of this roughly goes as follows: for each value in descending order, we consider the necessity of the operation. Then, we need the above number of times for the largest value, and if we do this number of operations beforehand, we can remove the part with this value and proceed.

Actually, we only need to consider edges that are minimal as segments in the graph. At the leftmost vertex, a cost of \(1\) is incurred; at the other vertices, a cost of \(0\) (\(1\)) is incurred if there is (not) an edge to the immediate left of it.

Thus, we can find the sum by subtracting from \(N \times M^N\) the total number of vertices with the cost \(0\). For a fixed edge \((i, j)\) and a fixed value \(A_i = x\), there are \(\sum_{i=0}^{N-1} \sum_{j=0}^{i-1} (\sum_{x=1}^{M} (M - x) ^{i-j-1}) * M^{N-(i-j)-1}\) sequences where \(j\) has the cost \(0\) because of this edge. This only depends on \(i-j\) and \(x\), so we can compute the sum in \(\mathrm{O}(NM)\) time.

Bonus: for how much value of \(N\) and \(M\) can you solve the problem?