View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 128M

Problem type

The unbalance of an array B is the maximum value of the array minus the minimum. Given an array A of length N, can you find the unbalance of every subarray of length K?

A subarray of an array A is defined as a set of consecutive elements in A


1\le N\le 10^5

1\le K\le N

1\le A_i\le 10^6

Input Specification

The first line contains two integers: N and K.

The second line contains N integers, the elements of A.

Output Specification

N-K+1 integers, the i-th of which is the unbalance of the subarray from the i-th index to the i+k-1-th index.

Sample Input

5 3
2 6 4 4 1

Sample Output

4 2 3

Sample Explanation

The three subarrays of length 3 are: [2,6,4], [6,4,4], and [4,4,1].

The first one has a maximum of 6 and a minimum of 2, so its unbalance is 6-2=4 The second one has an unbalance of 6-4=2 And the third has an unbalance of 4-1=3


There are no comments at the moment.