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 test-cases. The first line of each test-case will contain N, K, 1 < N ≤ 105 ,0 ≤ K ≤ 105 where N indicates number of plants.

Next line will contain N integers 0 ≤ hi ≤ 109 indicating height of i-th plant.

Sum of all N among all test-cases won't exceed 3*106

Output

For each test-case, print exactly one number - the biggest difference of plants near each other (biggest hi-hj such that |i-j|-1 ≤ 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: 2018-10-13 23:37:26

can use multiset or 2 deque for max and min for every [i....i+k+1] range

tusharjape: 2018-08-29 22:35:55


Last edit: 2018-08-29 22:36:38
vivek_dwivedi: 2018-06-06 12:08:44

Last edit: 2018-06-06 12:09:31
learnerinblack: 2018-05-24 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

PS: I found my mistake :p

Last edit: 2018-05-24 09:09:17
julkas: 2017-10-29 16:11:44

Different approach PQ.

Last edit: 2017-10-30 09:21:49
shahzada: 2017-03-24 06:47:30

Easy segment tree.

morass: 2016-09-13 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: 2016-09-08 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,:(
re:> @morass thanks,i am a beginner to algorithms but i still
don't think it is a N*K,

Last edit: 2016-09-15 16:57:20
morass: 2016-09-07 23:35:06

@ivo2001: Mistake was in statement! Thank you for pointing out! :)

ivo2001: 2016-09-07 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:2016-09-05
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU