この解説では、\(N,M \le 2000\) の解法を解説します。

まず、\(\max_{1 \le i < j \le N} (A_j - A_i)\) が負となるようなものについて解きます。

\(1 \le K \le M-1\) に対して、\(\max_{1 \le i < j \le N} (A_j - A_i)\) が \(-K\) 以下になるものの個数を求められればよいです。そのような個数は \(A\) に登場する数字を決めればよく、\(\displaystyle \binom{M-(N-1)(K-1)}{N}\) 通りあります。

以降、\(\max_{1 \le i < j \le N} (A_j - A_i)\) が正の場合について解きます。\(0 \le K \le M-1\) に対して、\(\max_{1 \le i < j \le N} (A_j - A_i)\) が \(K\) 以下であるものの個数が求められればよいです。

\(A\) の末尾に \(K+1\) を付け加えた数列 \(B\) と、\(B\) を末尾から見て厳密な最大値を取る部分だけで構成した数列 \(C\) を考えます。\(C\) に含まれる index の集合を固定した場合、\(C\) に含まれない index に対応する \(A_i\) は \(K+1\) 通りの値を取ることができます。

よって、\(\max_{1 \le i < j \le N} (A_j - A_i)\) が \(K\) 以下である数列の個数は、\(\displaystyle \sum_{|C|=1}^{N+1} (K+1)^{N+1-|C|} \times \binom{M-K-1}{|C|-1} \times \binom{N}{|C|-1}\) 通りです。

上記より、本問題を \(\mathrm{O}(NM)\) で解くことができます。