If an array is not diverse, it has fewer than ~K~ distinct elements present.

There are ~\frac{N^2+N}{2}~ subarrays, so we can enumerate the arrays which are not diverse and then the remaining ones must be diverse.

Lemma: Let ~f(i)~ be the leftmost index such that the subarray from ~f(i)~ to ~i~ is not diverse. If ~i \ge j~, then ~f(i) \ge f(j)~.

Proof: By contradiction - if ~i \ge j~ but ~f(i) < f(j)~, then we could extend ~f(j)~ to be at least as small as ~f(i)~ since that subarray would be a subarray of the array defined by ~f(i)~ and ~i~.

Therefore, if we loop ~i~ from left to right and maintain ~f(i)~ in amortized constant time, we can enumerate all the arrays which are not diverse. To do this, we advance ~i~ by one and maintain a frequency map of numbers to how many times we observe them. If the frequency map is at least ~K~ in size, we remove the leftmost element still present in the subarray and repeat this until the frequency map has size less than ~K~. The size of the remaining subarray is the number of subarrays ending at that index which are not diverse.