We will get the bivariate generating function $$$F(z, t) = \sum_{n\ge 1}\sum_{k=1}^n A_{n,k}\frac{z^nt^k}{n!}$$$, where $$$A_{n,k}$$$ is the sum of occurences of $$$k$$$ in all good sequence of length $$$n$$$. Consider the inclusion-exclution principle. For all contribution with $$$\max k = m$$$, we have
Which means that for all $$$i \in S$$$, we force all recurrences of $$$i$$$ are before $$$i + 1$$$, and the occurences of $$$j$$$ are counted.
Now our goal is to calculate
We consider $$$\left([z^n]\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}\right) + 1 = (1-t)[z^n] \frac 1{(1-z)(1-t\mathrm e^{z(1-t)})}$$$, which looks simpler.
Hence we have
Noticed that $$$[u^m]\mathrm{e}^{ku} = \frac{k^m}{m!}, [u^m] \frac1{(1-u)^k} = \binom{n+k-1}{n}$$$, this could be calculated straightly through multipoint evaluation with time complexity of $$$\Theta(n\log^2 n)$$$. It will pass if your implementation doesn't have a big constant.
It could also be improved to $$$\Theta(n\log n)$$$ through Lagrange Inversion formula, I leave this as a exercise.