Longest Subarray Within Threshold

You are given an array of integers and an integer threshold \( k \). Your task is to find the length of the longest contiguous subarray such that the difference between its maximum and minimum elements is at most \( k \).

Formally, given an array \( A = [a_1, a_2, \dots, a_n] \) and an integer \( k \), determine the maximum length \( L \) for which there exists an index range \( [i, j] \) (with \( 1 \le i \le j \le n \)) satisfying \[ \max\{a_i, a_{i+1}, \dots, a_j\} - \min\{a_i, a_{i+1}, \dots, a_j\} \le k. \]

This problem can be efficiently solved using a sliding window approach along with two deques to maintain the minimum and maximum elements in the current window.

inputFormat

The input begins with an integer \( T \) denoting the number of test cases. Each test case is described as follows:

• The first line of each test case contains two integers \( n \) and \( k \) \( (1 \leq n \leq \text{upper bound},\ k \ge 0) \), where \( n \) is the number of elements and \( k \) is the threshold.
• The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line containing the length of the longest contiguous subarray that satisfies the given condition.

## sample

3
5 3
1 3 5 7 9
5 5
1 3 5 7 9
1 3
1

2
3
1

</p>