Question1
You are given an array A of size N. Find the count of Good Subarrays in A. Since the answer may be a large return it modulo 10^9+7. A Good Subarray is one in which:- - The difference between minimum and second minimum elements is not more than D. - It is guaranteed that the size of the Good Subarray array is at least 2.
Input Format
- The first line contains an integer N, denoting the number of elements in A.
The second line contains D. The next i lines of N contains integer describing A[i]
Examples
Input 1
2 1 2 3
Output
0
Explanation
No Good Subarrays
Input 2
3 3 7 4 1
Output
3
Explanation
[0,1] , [0,2] , [1,2]
Input 3
3 1 3 7 8
Output
1
Explanation
[1,2]
I have a rather complicated idea:
1)compute 2 arrays, nsl[i] = closest position j to the left of i such that a[j]<=a[i] , and nsr[i] = closest position j to the right of i such that a[j] < a[i]. Both of them can be easily computed in o(n) using stack.
2)Now, if we consider a[i] is the minimum element, obviously, any subarray should be completely in the range [nsl[i] + 1, nsr[i]-1]. 3)find out the index, r of the leftmost element in the range [i+1,nsr[i]-1] such that a[r]<=a[i] + D, and the index l, of the rightmost element in the range [nsl[i]+1,i-1] such that a[l]<=a[i]+D. Both l,r can be found using binary search + sparse table.
4)Now, we can easily compute the number of good subarrays such that the minimum element is a[i]. if the subarray begins in the range [nsl[i]+1,l], then it can end anywhere in [i,nsr[i]-1]. Similarly, if it begins in the range [l+1,i], it can end anywhere in [r,nsr[i]-1].