You are standing at the start of a very long straight road. On the road, there are n cupcakes present. You are given the distance of each cupcake from the start of the road. Each of these distances is an integer, and multiple cupcakes can be present at the same distance from the start of the road.
You have to select 2 intervals of length k on the road and collect all the cupcakes that lie inside either of the intervals. The intervals are allowed to intersect.
For example, for k = 3, the interval [1, 4] is a valid interval of length 3, and by choosing that interval, you can collect all the cupcakes that lie at a distance of 1, 2, 3 or 4 from the start of the road.
Find the maximum number of cupcakes that you can collect by picking 2 intervals as described above.
Sample test case
n = 6
k = 1
distance = [1, 1, 2, 6, 8, 9]
expected output = 5
Explanation -
We can pick the 2 intervals [1, 2] and [8, 9]. Both these intervals have length of 1 and there are a total of 5 cupcakes that lie in these intervals
[execution time limit] 1 seconds (cpp)
[input] integer n
The number of cupcakes.
1 <= n <= 2 x (10^5)
[input] integer k
The length of the intervals that you can pick.
1 <= k <= 10^9
[input] array.integer distance
Array of n integers. The i th integer describes the distance of the i th cupcake from the start of the road.
1 <= Ai <= 10^9 , where Ai is the i th element in the array. All the Ais are NOT NECESSARILY DISTINCT.
[output] integer
The maximum number of cupcakes you can collect