Subarrays With At Least N Distinct Integers Given a sequence of integers and an integer N, output the number of contiguous subsequences that contain at least N distinct integers. Each integer in the sequence is non-negative and will not be larger than the size of the sequence.

For example, with the sequence 1,2,2,3 and N=2, there are 5 contiguous subsequences that contain at least 2 distinct integers:

1,2
1,2,2
2,2,3
2,3
1,2,2,3

The asymptotic time complexity must be linearithmic in the size of the input sequence. (The time complexity must be at most amortized O(S*logS) where S is the size of the input sequence.)
Testcases:




Sequence
N
Output




1,2,3
2
3


1,2,2,3
2
5


6,1,4,2,4,5
3
9


1,1,2,2,2,3,4,4
4
4


8,6,6,1,10,5,5,1,8,2
5
11


https://pastebin.com/E8Xaej8f (1,000 integers)
55
446308


https://pastebin.com/4aqiD8BL (80,000 integers)
117
3190760620
JavaScript (ES6), 93 bytes
Saved 18 bytes thanks to @user81655
Saved 2 bytes thanks to @tsh
Expects (N)(sequence).

n=&gt;C=a=&gt;eval('for(i=j=a.length,c=s=0;~j;c+=c&lt;n?(C[v=a[--j]]=-~C[v])&lt;2:-!--C[s-=~j,a[--i]])s')

Try it online!