ADAPLANT  Ada and Plants
Ada the Ladybug has grown many plants. She was trying to grow all plants with equal size. Now she is wondering about the biggest difference between heights of two plants which are near each other. Plants are near each other, if there are at most K plants between them.
Input
The first line contains T, the number of testcases. The first line of each testcase will contain N, K, 1 < N ≤ 10^{5} ,0 ≤ K ≤ 10^{5} where N indicates number of plants.Next line will contain N integers 0 ≤ h_{i} ≤ 10^{9} indicating height of ith plant.
Sum of all N among all testcases won't exceed 3*10^{6}
Output
For each testcase, print exactly one number  the biggest difference of plants near each other (biggest h_{i}h_{j} such that ij1 ≤ K).Example Input
3 5 0 1 2 3 5 6 4 6 1 10 2 9 10 1 1 7 8 9 19 11 21 8 11 0
Example Output
2 9 13
hide comments
hsraktu:
20181013 23:37:26
can use multiset or 2 deque for max and min for every [i....i+k+1] range 

tusharjape:
20180829 22:35:55


vivek_dwivedi:
20180606 12:08:44
Last edit: 20180606 12:09:31 

learnerinblack:
20180524 08:33:37
@morass I am trying to solve this by square root decomposition method(time complexity O(sqrt(N)*N)  correct me if i am wrong) but I don't know why it is giving wrong answer after test case 10. I am new to this concept so it would be of great help if you could point out my mistake


julkas:
20171029 16:11:44
Different approach PQ. Last edit: 20171030 09:21:49 

shahzada:
20170324 06:47:30
Easy segment tree. 

morass:
20160913 14:55:15
@rajat_kumar: Hi, maybe I've looked badly, but your algo seems N*K to me (so if I'm not wrong, then you have to improve algorithm :'( ) 

rajat_kumar:
20160908 13:04:21
@morass can you please look at my code and tell if i am getting TLE due to lack of optimisation or a faulty algo,:(


morass:
20160907 23:35:06
@ivo2001: Mistake was in statement! Thank you for pointing out! :) 

ivo2001:
20160907 23:04:28
In the statement is written that N and K will be bigger than 1, but in the first sample K is equal to 0 is the mistake in the statement or in the sample? 
Added by:  Morass 
Date:  20160905 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 