Codeforces Round #572 (Div. 1) C. Array Beauty

https://codeforces.com/contest/1188/problem/C

Suppose that the array is already sorted. Let f(x) be the number of subarrays such that any difference between adjacent elements is greater than or equal to x. We then have the answer as f(1)+f(2)+f(3)+....

Since it takes O(NK) to calculate f(x), we may think the total complexity become O(NK max A). However, actually, we only have to calculate upto f(N/K), so the true time complexity is O(NK max A / K), that is O(N max A). It is fast enough.