We are given an integer k (size of an interval) and an array A. Since we know every element in the array can be a part of at most k intervals of size k, we need to construct an array B where B[i] represents the maximum value of

abs(A[i] — p) — abs(A[i] — q)

over all intervals that A[i] is part of(at most k intervals), here p denotes the maximum value in the interval and q represents the minimum value in the interval.

Expected time complexity is O(n).