Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
 
Example 1:
Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:
Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:
Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

 
Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        

Solutions:
from collections import deque

class Solution:

	def longestSubarray(self, nums, limit):
		(maxQ, minQ) = (deque(), deque())
		i = 0
		res = 0
		for (j, val) in enumerate(nums):
			while maxQ and val > maxQ[-1]:
				maxQ.pop()
			while minQ and val < minQ[-1]:
				minQ.pop()
			maxQ.append(val)
			minQ.append(val)
			if maxQ[0] - minQ[0] > limit:
				if maxQ[0] == nums[i]:
					maxQ.popleft()
				if minQ[0] == nums[i]:
					minQ.popleft()
				i += 1
			res = max(res, j - i + 1)
		return res
from collections import deque

class Solution:

	def longestSubarray(self, nums, limit):
		(maxQ, minQ) = (deque(), deque())
		i = 0
		for val in nums:
			while maxQ and val > maxQ[-1]:
				maxQ.pop()
			while minQ and val < minQ[-1]:
				minQ.pop()
			maxQ.append(val)
			minQ.append(val)
			if maxQ[0] - minQ[0] > limit:
				if maxQ[0] == nums[i]:
					maxQ.popleft()
				if minQ[0] == nums[i]:
					minQ.popleft()
				i += 1
		return len(nums) - i


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(minHeap, maxHeap) = ([], [])
		left = maxLen = 0
		for right in range(len(nums)):
			heappush(minHeap, (nums[right], right))
			heappush(maxHeap, (-nums[right], right))
			while nums[right] - minHeap[0][0] > limit:
				left = max(left, heappop(minHeap)[1] + 1)
			while -maxHeap[0][0] - nums[right] > limit:
				left = max(left, heappop(maxHeap)[1] + 1)
			maxLen = max(maxLen, right - left + 1)
		return maxLen


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) < 2:
			return 1
		longestSize = 1
		left = 0
		(lo_q, hi_q) = ([], [])
		heapq.heappush(lo_q, (nums[0], 0))
		heapq.heappush(hi_q, (-nums[0], 0))
		for idx in range(1, len(nums)):
			if lo_q and nums[idx] < lo_q[0][0]:
				lo_q = []
			elif hi_q and -nums[idx] < hi_q[0][0]:
				hi_q = []
			heapq.heappush(lo_q, (nums[idx], idx))
			heapq.heappush(hi_q, (-nums[idx], idx))
			while lo_q and abs(nums[idx] - lo_q[0][0]) > limit:
				left = max(left, heapq.heappop(lo_q)[1] + 1)
			while hi_q and abs(nums[idx] + hi_q[0][0]) > limit:
				left = max(left, heapq.heappop(hi_q)[1] + 1)
			longestSize = max(longestSize, idx - left + 1)
		return longestSize


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_heap = []
		max_heap = []
		start = 0
		best = 0
		for (idx, val) in enumerate(nums):
			heappush(min_heap, (val, idx))
			heappush(max_heap, (-val, idx))
			while start < idx and abs(min_heap[0][0] + max_heap[0][0]) > limit:
				start += 1
				while min_heap[0][1] < start:
					heappop(min_heap)
				while max_heap[0][1] < start:
					heappop(max_heap)
			best = max(best, idx - start + 1)
		return best


from heapq import *

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minH = []
		maxH = []
		l = 0
		ans = 0
		for (r, n) in enumerate(nums):
			heappush(minH, (n, r))
			heappush(maxH, (-n, r))
			while -maxH[0][0] - minH[0][0] > limit:
				l = min(maxH[0][1], minH[0][1]) + 1
				while maxH[0][1] < l:
					heappop(maxH)
				while minH[0][1] < l:
					heappop(minH)
			ans = max(ans, r - l + 1)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		import heapq
		(mnq, mxq) = ([], [])
		res = 0
		left = -1
		for (right, num) in enumerate(nums):
			heapq.heappush(mnq, (num, right))
			heapq.heappush(mxq, (-num, right))
			while -mxq[0][0] - mnq[0][0] > limit:
				left = min(mnq[0][1], mxq[0][1])
				while mxq[0][1] <= left:
					heapq.heappop(mxq)
				while mnq[0][1] <= left:
					heapq.heappop(mnq)
			res = max(res, right - left)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		minh = []
		maxh = []
		start = 0
		ans = 0
		deleted = set()
		for end in range(n):
			x = nums[end]
			heappush(minh, (x, end))
			heappush(maxh, (-x, end))
			while minh and minh[0][1] in deleted:
				heappop(minh)
			while maxh and maxh[0][1] in deleted:
				heappop(maxh)
			while minh and maxh and (-maxh[0][0] - minh[0][0] > limit) and (start <= end):
				deleted.add(start)
				start += 1
				while minh and minh[0][1] in deleted:
					heappop(minh)
				while maxh and maxh[0][1] in deleted:
					heappop(maxh)
			ans = max(ans, end - start + 1)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(min_heap, max_heap) = (deque([0]), deque([0]))
		res = 1
		far = -1
		for i in range(1, len(nums)):
			while min_heap and nums[min_heap[-1]] > nums[i]:
				min_heap.pop()
			while max_heap and nums[max_heap[-1]] < nums[i]:
				max_heap.pop()
			while min_heap and abs(nums[min_heap[0]] - nums[i]) > limit:
				far = max(far, min_heap.popleft())
			while max_heap and abs(nums[max_heap[0]] - nums[i]) > limit:
				far = max(far, max_heap.popleft())
			res = max(res, i - far)
			min_heap.append(i)
			max_heap.append(i)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		minDeque = collections.deque()
		maxDeque = collections.deque()
		maxlength = 0
		left = 0
		right = 0
		while right < len(nums):
			while maxDeque and nums[right] > nums[maxDeque[-1]]:
				maxDeque.pop()
			maxDeque.append(right)
			while minDeque and nums[right] < nums[minDeque[-1]]:
				minDeque.pop()
			minDeque.append(right)
			while abs(nums[maxDeque[0]] - nums[minDeque[0]]) > limit:
				if maxDeque[0] == left:
					maxDeque.popleft()
				if minDeque[0] == left:
					minDeque.popleft()
				left += 1
			maxlength = max(maxlength, right - left + 1)
			right += 1
		return maxlength


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minHeap = []
		maxHeap = []
		l = 0
		maxSize = 0
		for (r, num) in enumerate(nums):
			heappush(minHeap, (num, r))
			heappush(maxHeap, (-num, r))
			(minElement, minIndex) = minHeap[0]
			(maxElement, maxIndex) = maxHeap[0]
			maxElement = -maxElement
			while maxElement - minElement > limit:
				l += 1
				while minHeap[0][1] < l:
					heappop(minHeap)
				while maxHeap[0][1] < l:
					heappop(maxHeap)
				(minElement, minIndex) = minHeap[0]
				(maxElement, maxIndex) = maxHeap[0]
				maxElement = -maxElement
			curSize = r - l + 1
			maxSize = max(curSize, maxSize)
		return maxSize


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxHeap = []
		minHeap = []
		ans = 0
		i = 0
		for j in range(len(nums)):
			heapq.heappush(maxHeap, (-nums[j], j))
			heapq.heappush(minHeap, (nums[j], j))
			while -maxHeap[0][0] - minHeap[0][0] > limit:
				i = min(maxHeap[0][1], minHeap[0][1]) + 1
				while maxHeap[0][1] < i:
					heapq.heappop(maxHeap)
				while minHeap[0][1] < i:
					heapq.heappop(minHeap)
			ans = max(ans, j - i + 1)
		return ans


import collections

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minDeque = collections.deque()
		maxDeque = collections.deque()
		start = end = 0
		ans = 0
		while end < len(nums):
			n = nums[end]
			while len(minDeque) > 0 and nums[minDeque[-1]] >= n:
				minDeque.pop()
			minDeque.append(end)
			while len(maxDeque) > 0 and nums[maxDeque[-1]] <= n:
				maxDeque.pop()
			maxDeque.append(end)
			if nums[maxDeque[0]] - nums[minDeque[0]] > limit:
				start += 1
				while len(minDeque) > 0 and minDeque[0] < start:
					minDeque.popleft()
				while len(maxDeque) > 0 and maxDeque[0] < start:
					maxDeque.popleft()
			else:
				ans = max(ans, end - start + 1)
				end += 1
		return ans


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(minheap, maxheap) = ([], [])
		start = 0
		res = 0
		for (j, elem) in enumerate(nums):
			heapq.heappush(minheap, (elem, j))
			heapq.heappush(maxheap, (-elem, j))
			while -maxheap[0][0] - minheap[0][0] > limit:
				start = min(minheap[0][1], maxheap[0][1]) + 1
				while maxheap[0][1] < start:
					heapq.heappop(maxheap)
				while minheap[0][1] < start:
					heapq.heappop(minheap)
			res = max(res, j - start + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		(i, j, ans) = (0, 0, 0)
		(min_heap, max_heap) = ([], [])
		heapq.heapify(min_heap)
		heapq.heapify(max_heap)
		while i <= j < n:
			heapq.heappush(min_heap, (nums[j], j))
			heapq.heappush(max_heap, (-nums[j], j))
			while i <= j < n and -max_heap[0][0] - min_heap[0][0] > limit:
				i += 1
				while min_heap and min_heap[0][1] < i:
					heapq.heappop(min_heap)
				while max_heap and max_heap[0][1] < i:
					heapq.heappop(max_heap)
			ans = max(ans, j - i + 1)
			j += 1
		return ans


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		longest = 0
		mins = []
		maxs = []
		start = 0
		i = 0
		while i < len(nums):
			x = nums[i]
			heapq.heappush(mins, (x, i))
			heapq.heappush(maxs, (-x, i))
			(currMin, currMax) = (mins[0][0], -maxs[0][0])
			while mins and maxs and (currMax - currMin > limit):
				start += 1
				while mins[0][1] < start:
					heapq.heappop(mins)
				while maxs[0][1] < start:
					heapq.heappop(maxs)
				(currMin, currMax) = (mins[0][0], -maxs[0][0])
			longest = max(longest, i - start + 1)
			i += 1
		return longest


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(minheap, maxheap) = ([], [])
		res = 0
		i = 0
		for (j, n) in enumerate(nums):
			heapq.heappush(minheap, (n, j))
			heapq.heappush(maxheap, (-n, j))
			while -maxheap[0][0] - minheap[0][0] > limit:
				i = min(maxheap[0][1], minheap[0][1]) + 1
				while maxheap[0][1] < i:
					heapq.heappop(maxheap)
				while minheap[0][1] < i:
					heapq.heappop(minheap)
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxq, minq) = ([], [])
		res = i = 0
		for (j, num) in enumerate(nums):
			heappush(maxq, (-num, j))
			heappush(minq, (num, j))
			while -maxq[0][0] - minq[0][0] > limit:
				i = min(maxq[0][1], minq[0][1]) + 1
				while maxq[0][1] < i:
					heappop(maxq)
				while minq[0][1] < i:
					heappop(minq)
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestSubarray(self, A, limit):
		M = collections.deque()
		m = collections.deque()
		i = 0
		for a in A:
			while M and a > M[-1]:
				M.pop()
			while m and a < m[-1]:
				m.pop()
			M.append(a)
			m.append(a)
			if M[0] - m[0] > limit:
				if M[0] == A[i]:
					M.popleft()
				if m[0] == A[i]:
					m.popleft()
				i += 1
		return len(A) - i


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums or len(nums) == 0:
			return 0
		minDeque = deque()
		maxDeque = deque()
		left = 0
		right = 0
		result = 0
		while right < len(nums):
			while minDeque and nums[right] < nums[minDeque[-1]]:
				minDeque.pop()
			while maxDeque and nums[right] > nums[maxDeque[-1]]:
				maxDeque.pop()
			minDeque.append(right)
			maxDeque.append(right)
			while nums[maxDeque[0]] - nums[minDeque[0]] > limit:
				while maxDeque[0] <= left:
					maxDeque.popleft()
				while minDeque[0] <= left:
					minDeque.popleft()
				left += 1
			result = max(result, right - left + 1)
			right += 1
		return result


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		n = len(nums)
		i = j = 0
		curr_max = curr_min = nums[0]
		maxes = [(-curr_max, 0)]
		mins = [(curr_min, 0)]
		best = 0
		while i <= j < n:
			if abs(-maxes[0][0] - mins[0][0]) <= limit:
				best = max(best, j - i + 1)
				j += 1
				if j < n:
					heapq.heappush(maxes, (-nums[j], j))
					heapq.heappush(mins, (nums[j], j))
			else:
				i += 1
				while not i <= maxes[0][1] <= j:
					heapq.heappop(maxes)
				while not i <= mins[0][1] <= j:
					heapq.heappop(mins)
		return best


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		ans = 1
		i = j = 0
		minHeap = [(nums[0], 0)]
		maxHeap = [(-nums[0], 0)]
		while j < len(nums):
			while minHeap[0][1] < i:
				heapq.heappop(minHeap)
			while maxHeap[0][1] < i:
				heapq.heappop(maxHeap)
			if -maxHeap[0][0] - minHeap[0][0] > limit:
				i += 1
			else:
				j += 1
				ans = max(ans, j - i)
				if j < len(nums):
					heapq.heappush(minHeap, (nums[j], j))
					heapq.heappush(maxHeap, (-nums[j], j))
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) <= 1:
			return len(nums)
		queue = [nums[0]]
		small = queue[0]
		large = queue[0]
		ans = 1
		for i in range(1, len(nums)):
			if abs(nums[i] - small) <= limit and abs(nums[i] - large) <= limit:
				queue.append(nums[i])
				small = min(small, nums[i])
				large = max(large, nums[i])
				ans = max(ans, len(queue))
			else:
				if ans > len(nums) // 2:
					break
				while queue and (not (abs(nums[i] - small) <= limit and abs(nums[i] - large) <= limit)):
					queue.pop(0)
					if queue:
						small = min(queue)
						large = max(queue)
					else:
						break
				if queue:
					queue.append(nums[i])
					small = min(queue)
					large = max(queue)
				else:
					queue = [nums[i]]
					small = nums[i]
					large = nums[i]
		return ans


class Solution:

	def longestSubarray(self, A, limit):
		(maxq, minq) = ([], [])
		res = i = 0
		for (j, a) in enumerate(A):
			heapq.heappush(maxq, [-a, j])
			heapq.heappush(minq, [a, j])
			while -maxq[0][0] - minq[0][0] > limit:
				i = min(maxq[0][1], minq[0][1]) + 1
				while maxq[0][1] < i:
					heapq.heappop(maxq)
				while minq[0][1] < i:
					heapq.heappop(minq)
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(max_heap, min_heap) = ([], [])
		res = 0
		l = 0
		for (r, a) in enumerate(nums):
			heapq.heappush(max_heap, [-a, r])
			heapq.heappush(min_heap, [a, r])
			while -max_heap[0][0] - min_heap[0][0] > limit:
				while max_heap[0][1] <= l:
					heapq.heappop(max_heap)
				while min_heap[0][1] <= l:
					heapq.heappop(min_heap)
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def longestSubarray(self, A: List[int], limit: int) -> int:
		maxd = collections.deque()
		mind = collections.deque()
		i = 0
		for a in A:
			while maxd and a > maxd[-1]:
				maxd.pop()
			while mind and a < mind[-1]:
				mind.pop()
			maxd.append(a)
			mind.append(a)
			if maxd[0] - mind[0] > limit:
				if maxd[0] == A[i]:
					maxd.popleft()
				if mind[0] == A[i]:
					mind.popleft()
				i += 1
		return len(A) - i


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		ans = 0
		(maxq, minq) = ([], [])
		i = 0
		for num in nums:
			while maxq and maxq[-1] < num:
				maxq.pop()
			while minq and minq[-1] > num:
				minq.pop()
			maxq.append(num)
			minq.append(num)
			if maxq[0] - minq[0] > limit:
				if maxq[0] == nums[i]:
					maxq.pop(0)
				if minq[0] == nums[i]:
					minq.pop(0)
				i += 1
		return len(nums) - i


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(hmin, hmax) = ([], [])
		(heapq.heapify(hmin), heapq.heapify(hmax))
		max_length = 0
		(i, j) = (0, 0)
		(heapq.heappush(hmin, (nums[0], 0)), heapq.heappush(hmax, (-1 * nums[0], 0)))
		while j < len(nums):
			while hmax[0][1] < i:
				heapq.heappop(hmax)
			while hmin[0][1] < i:
				heapq.heappop(hmin)
			if -1 * (hmax[0][0] + hmin[0][0]) <= limit:
				max_length = max(max_length, j - i + 1)
				j += 1
				if j >= len(nums):
					break
				heapq.heappush(hmin, (nums[j], j))
				heapq.heappush(hmax, (-1 * nums[j], j))
			else:
				i += 1
		return max_length


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxheap, minheap) = ([(-nums[0], 0)], [(nums[0], 0)])
		(l, maxindex, res) = (0, 0, 1)
		for (i, val) in enumerate(nums[1:], 1):
			if val - minheap[0][0] <= limit and -maxheap[0][0] - val <= limit:
				res = max(res, i - maxindex + 1)
			else:
				while minheap and val - minheap[0][0] > limit:
					(v, index) = heapq.heappop(minheap)
					maxindex = max(maxindex, index + 1)
				while maxheap and -maxheap[0][0] - val > limit:
					(v, index) = heapq.heappop(maxheap)
					maxindex = max(maxindex, index + 1)
			heapq.heappush(minheap, (val, i))
			heapq.heappush(maxheap, (-val, i))
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maximums = [(-nums[0], 0)]
		minimums = [(nums[0], 0)]
		left = 0 if len(nums) > 1 else 1
		right = 1
		while right < len(nums):
			heapq.heappush(maximums, (-nums[right], right))
			heapq.heappush(minimums, (nums[right], right))
			right += 1
			while maximums[0][1] < left:
				heapq.heappop(maximums)
			while minimums[0][1] < left:
				heapq.heappop(minimums)
			while -maximums[0][0] - minimums[0][0] <= limit and right < len(nums):
				heapq.heappush(maximums, (-nums[right], right))
				heapq.heappush(minimums, (nums[right], right))
				right += 1
			left += 1
		if -maximums[0][0] - minimums[0][0] <= limit:
			return right - left + 1
		else:
			return right - left


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxq, minq) = ([], [])
		(l, r) = (0, 0)
		res = 0
		for r in range(len(nums)):
			heapq.heappush(maxq, [-nums[r], r])
			heapq.heappush(minq, [nums[r], r])
			while -maxq[0][0] - minq[0][0] > limit:
				l = min(maxq[0][1], minq[0][1]) + 1
				while maxq[0][1] < l:
					heapq.heappop(maxq)
				while minq[0][1] < l:
					heapq.heappop(minq)
			res = max(res, r - l + 1)
		return res


from heapq import heapify, heappop, heappush

class Solution:

	def longestSubarray(self, lis: List[int], limit: int) -> int:
		n = len(lis)
		miheap = []
		mxheap = []
		heapify(miheap)
		heapify(mxheap)
		ans = 1
		heappush(miheap, [lis[0], 0])
		heappush(mxheap, [-lis[0], 0])
		tmp = 0
		for i in range(1, n):
			heappush(miheap, [lis[i], i])
			heappush(mxheap, [-lis[i], i])
			while miheap and abs(miheap[0][0] + mxheap[0][0]) > limit:
				tmp = min(mxheap[0][1], miheap[0][1]) + 1
				while mxheap[0][1] < tmp:
					heapq.heappop(mxheap)
				while miheap[0][1] < tmp:
					heapq.heappop(miheap)
			ans = max(ans, i - tmp + 1)
		return ans


from heapq import *
from collections import Counter

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_heap = []
		max_heap = []
		lazy_delete_min_heap = Counter()
		lazy_delete_max_heap = Counter()
		l = 0
		longest = 0
		for r in range(len(nums)):
			heappush(min_heap, nums[r])
			heappush(max_heap, -nums[r])
			while abs(nums[r] - min_heap[0]) > limit or abs(nums[r] + max_heap[0]) > limit:
				lazy_delete_min_heap[nums[l]] += 1
				lazy_delete_max_heap[nums[l]] += 1
				while lazy_delete_min_heap[min_heap[0]] > 0:
					lazy_delete_min_heap[min_heap[0]] -= 1
					heappop(min_heap)
				while lazy_delete_max_heap[-max_heap[0]] > 0:
					lazy_delete_max_heap[-max_heap[0]] -= 1
					heappop(max_heap)
				l += 1
			longest = max(longest, r - l + 1)
		return longest


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(min_deque, max_deque) = (deque(), deque())
		l = r = 0
		ans = 0
		while r < len(nums):
			while min_deque and nums[r] <= nums[min_deque[-1]]:
				min_deque.pop()
			while max_deque and nums[r] >= nums[max_deque[-1]]:
				max_deque.pop()
			min_deque.append(r)
			max_deque.append(r)
			if nums[max_deque[0]] - nums[min_deque[0]] <= limit:
				ans = max(ans, r - l + 1)
				r += 1
			elif nums[max_deque[0]] - nums[min_deque[0]] > limit:
				while min_deque[0] <= l:
					min_deque.popleft()
				while max_deque[0] <= l:
					max_deque.popleft()
				l += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		begin = end = 0
		l = len(nums)
		d = 0
		heap_min = []
		heap_max = []
		heapq.heapify(heap_min)
		heapq.heapify(heap_max)
		while end < l:
			heapq.heappush(heap_min, (nums[end], end))
			heapq.heappush(heap_max, (-1 * nums[end], end))
			while len(heap_min) > 0 and nums[end] - heap_min[0][0] > limit:
				(value, idx) = heapq.heappop(heap_min)
				begin = max(begin, idx + 1)
			while len(heap_max) > 0 and -heap_max[0][0] - nums[end] > limit:
				(value, idx) = heapq.heappop(heap_max)
				begin = max(begin, idx + 1)
			if end - begin + 1 > d:
				d = end - begin + 1
			end += 1
		return d


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		N = len(nums)
		if N == 0:
			return 0
		minQ = []
		maxQ = []
		l = 0
		maxL = 0
		for r in range(N):
			num = nums[r]
			idx_rightmost = l - 1
			while minQ and (num - minQ[0][0] > limit or minQ[0][1] <= idx_rightmost):
				[val, idx] = heapq.heappop(minQ)
				idx_rightmost = max(idx_rightmost, idx)
			while maxQ and (-maxQ[0][0] - num > limit or maxQ[0][1] <= idx_rightmost):
				[val, idx] = heapq.heappop(maxQ)
				idx_rightmost = max(idx_rightmost, idx)
			l = idx_rightmost + 1
			heapq.heappush(minQ, [nums[r], r])
			heapq.heappush(maxQ, [-nums[r], r])
			maxL = max(maxL, r - l + 1)
		return maxL


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		small = []
		large = []
		res = 1
		left = 0
		for i in range(len(nums)):
			while small and nums[small[-1]] > nums[i]:
				small.pop()
			while large and nums[large[-1]] < nums[i]:
				large.pop()
			small.append(i)
			large.append(i)
			if small and large and (nums[large[0]] - nums[small[0]] > limit):
				left += 1
				if small[0] < left:
					small.pop(0)
				if large[0] < left:
					large.pop(0)
			res = max(res, i - left + 1)
		return res


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		length = len(nums)
		start = 0
		min_heap = []
		max_heap = []
		res = 1
		for (i, num) in enumerate(nums):
			heapq.heappush(min_heap, (num, -i))
			heapq.heappush(max_heap, (-num, -i))
			while -max_heap[0][0] - min_heap[0][0] > limit:
				start += 1
				while -min_heap[0][1] < start:
					heapq.heappop(min_heap)
				while -max_heap[0][1] < start:
					heapq.heappop(max_heap)
			res = max(res, i - start + 1)
		return res


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minQue = deque()
		maxQue = deque()
		(start, end) = (0, 0)
		longest = 1
		while end < len(nums):
			current = nums[end]
			while minQue and nums[minQue[-1]] >= current:
				minQue.pop()
			minQue.append(end)
			while maxQue and nums[maxQue[-1]] <= current:
				maxQue.pop()
			maxQue.append(end)
			if nums[maxQue[0]] - nums[minQue[0]] > limit:
				start += 1
				while maxQue and start > maxQue[0]:
					maxQue.popleft()
				while minQue and start > minQue[0]:
					minQue.popleft()
			else:
				longest = max(longest, end - start + 1)
				end += 1
		return longest


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		from collections import deque
		mnq = deque([])
		mxq = deque([])
		left = 0
		for (right, num) in enumerate(nums):
			while mxq and mxq[-1] < num:
				mxq.pop()
			while mnq and mnq[-1] > num:
				mnq.pop()
			mxq.append(num)
			mnq.append(num)
			if mxq[0] - mnq[0] > limit:
				if mxq[0] == nums[left]:
					mxq.popleft()
				if mnq[0] == nums[left]:
					mnq.popleft()
				left += 1
		return len(nums) - left


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		hq = deque()
		hq.append([nums[0], 0])
		lq = deque()
		lq.append([nums[0], 0])
		l = 0
		ans = 1
		for i in range(1, len(nums)):
			n = nums[i]
			while hq[0][1] < l:
				hq.popleft()
			while lq[0][1] < l:
				lq.popleft()
			while hq and hq[-1][0] <= n:
				hq.pop()
			else:
				hq.append([n, i])
			while lq and lq[-1][0] >= n:
				lq.pop()
			else:
				lq.append([n, i])
			if hq[0][0] - n > limit:
				ans = max(ans, i - l)
				while hq[0][0] - n > limit:
					l = hq[0][1] + 1
					hq.popleft()
			elif n - lq[0][0] > limit:
				ans = max(ans, i - l)
				while n - lq[0][0] > limit:
					l = lq[0][1] + 1
					lq.popleft()
			else:
				ans = max(ans, i - l + 1)
		return ans


class Solution:

	def longestSubarray(self, A: List[int], limit: int) -> int:
		import heapq
		maxd = []
		mind = []
		res = i = 0
		for (j, a) in enumerate(A):
			heapq.heappush(maxd, [-a, j])
			heapq.heappush(mind, [a, j])
			while -maxd[0][0] - mind[0][0] > limit:
				i = min(maxd[0][1], mind[0][1]) + 1
				while maxd[0][1] < i:
					heapq.heappop(maxd)
				while mind[0][1] < i:
					heapq.heappop(mind)
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(begin, end) = (0, 0)
		n = len(nums)
		heap_min = []
		heapq.heapify(heap_min)
		heap_max = []
		heapq.heapify(heap_max)
		heapq.heappush(heap_min, (nums[0], 0))
		heapq.heappush(heap_max, (-nums[0], 0))
		max_length = 1
		while end < n - 1:
			end += 1
			if abs(nums[end] - heap_min[0][0]) > limit or abs(-heap_max[0][0] - nums[end]) > limit:
				while len(heap_min) > 0 and nums[end] - heap_min[0][0] > limit:
					(value, idx) = heapq.heappop(heap_min)
					begin = max(begin, idx + 1)
				while len(heap_max) > 0 and -heap_max[0][0] - nums[end] > limit:
					(value, idx) = heapq.heappop(heap_max)
					begin = max(begin, idx + 1)
			heapq.heappush(heap_min, (nums[end], end))
			heapq.heappush(heap_max, (-nums[end], end))
			max_length = max(max_length, end - begin + 1)
		return max_length


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		res = i = 0
		maxh = []
		minh = []
		for (j, val) in enumerate(nums):
			heapq.heappush(maxh, [-val, j])
			heapq.heappush(minh, [val, j])
			while -maxh[0][0] - minh[0][0] > limit:
				i = min(maxh[0][1], minh[0][1]) + 1
				while maxh[0][1] < i:
					heapq.heappop(maxh)
				while minh[0][1] < i:
					heapq.heappop(minh)
			res = max(res, j - i + 1)
		return res


class minMonotonicQueue(object):

	def __init__(self):
		self.queue = collections.deque([])

	def push(self, num, idx):
		while len(self.queue) != 0 and self.queue[-1][0] > num:
			self.queue.pop()
		self.queue.append((num, idx))

	def pop(self, idx):
		if self.queue[0][1] == idx:
			self.queue.popleft()

class maxMonotonicQueue(object):

	def __init__(self):
		self.queue = collections.deque([])

	def push(self, num, idx):
		while len(self.queue) != 0 and self.queue[-1][0] < num:
			self.queue.pop()
		self.queue.append((num, idx))

	def pop(self, idx):
		if self.queue[0][1] == idx:
			self.queue.popleft()

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(ptr1, ptr2) = (0, 0)
		res = 0
		(minQ, maxQ) = (minMonotonicQueue(), maxMonotonicQueue())
		while ptr1 < len(nums) and ptr2 < len(nums):
			minQ.push(nums[ptr2], ptr2)
			maxQ.push(nums[ptr2], ptr2)
			while maxQ.queue[0][0] - minQ.queue[0][0] > limit:
				ptr1 += 1
				if ptr1 > maxQ.queue[0][1]:
					maxQ.pop(maxQ.queue[0][1])
				if ptr1 > minQ.queue[0][1]:
					minQ.pop(minQ.queue[0][1])
			res = max(res, ptr2 - ptr1 + 1)
			ptr2 += 1
		return res


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		res = 1
		slow = 0
		fast = 0
		min_queue = deque()
		max_queue = deque()
		while fast < len(nums):
			while min_queue and nums[fast] <= nums[min_queue[-1]]:
				min_queue.pop()
			while max_queue and nums[fast] >= nums[max_queue[-1]]:
				max_queue.pop()
			min_queue.append(fast)
			max_queue.append(fast)
			while nums[max_queue[0]] - nums[min_queue[0]] > limit:
				slow += 1
				if max_queue[0] < slow:
					max_queue.popleft()
				if min_queue[0] < slow:
					min_queue.popleft()
			res = max(res, fast - slow + 1)
			fast += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_q = deque()
		min_q = deque()
		left = 0
		result = 0
		for (i, n) in enumerate(nums):
			while max_q and nums[max_q[-1]] <= n:
				max_q.pop()
			max_q.append(i)
			while min_q and nums[min_q[-1]] >= n:
				min_q.pop()
			min_q.append(i)
			while left < i and nums[max_q[0]] - nums[min_q[0]] > limit:
				if left == max_q[0]:
					max_q.popleft()
				if left == min_q[0]:
					min_q.popleft()
				left += 1
			result = max(result, i - left + 1)
		return result


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxq = []
		minq = []
		left = 0
		res = 0
		for (right, num) in enumerate(nums):
			heapq.heappush(maxq, [-num, right])
			heapq.heappush(minq, [num, right])
			while -maxq[0][0] - minq[0][0] > limit:
				left = min(maxq[0][1], minq[0][1]) + 1
				while maxq[0][1] < left:
					heapq.heappop(maxq)
				while minq[0][1] < left:
					heapq.heappop(minq)
			res = max(res, right - left + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxq, minq) = ([], [])
		res = i = 0
		for (pos, val) in enumerate(nums):
			heapq.heappush(maxq, [-val, pos])
			heapq.heappush(minq, [val, pos])
			while -maxq[0][0] - minq[0][0] > limit:
				i = min(maxq[0][1], minq[0][1]) + 1
				while maxq[0][1] < i:
					heapq.heappop(maxq)
				while minq[0][1] < i:
					heapq.heappop(minq)
			res = max(res, pos - i + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxq, minq) = ([], [])
		best = i = 0
		for (j, a) in enumerate(nums):
			heapq.heappush(maxq, (-a, j))
			heapq.heappush(minq, (a, j))
			while -maxq[0][0] - minq[0][0] > limit:
				i = min(maxq[0][1], minq[0][1]) + 1
				while maxq[0][1] < i:
					heapq.heappop(maxq)
				while minq[0][1] < i:
					heapq.heappop(minq)
			best = max(best, j - i + 1)
		return best


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxd, mind) = (collections.deque(), collections.deque())
		(l, r, res) = (0, 0, 0)
		while r < len(nums):
			while len(maxd) and maxd[-1] < nums[r]:
				maxd.pop()
			while len(mind) and mind[-1] > nums[r]:
				mind.pop()
			maxd.append(nums[r])
			mind.append(nums[r])
			while maxd[0] - mind[0] > limit:
				if nums[l] == maxd[0]:
					maxd.popleft()
				if nums[l] == mind[0]:
					mind.popleft()
				l += 1
			res = max(r - l + 1, res)
			r += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		if len(nums) == 1:
			return 1
		left = 0
		right = 0
		curr_min = nums[0]
		curr_max = nums[0]
		max_len = 1
		for right in range(len(nums)):
			curr_max = max(curr_max, nums[right])
			curr_min = min(curr_min, nums[right])
			if curr_max - curr_min <= limit:
				max_len = max(max_len, right - left + 1)
			else:
				if nums[left] == curr_max:
					curr_max = max(nums[left + 1:right + 1])
				if nums[left] == curr_min:
					curr_min = min(nums[left + 1:right + 1])
				left += 1
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		currmax = currmin = nums[0]
		start = 0
		res = 1
		for i in range(1, len(nums)):
			currmax = max(currmax, nums[i])
			currmin = min(currmin, nums[i])
			if currmax - currmin <= limit:
				res = max(res, i - start + 1)
			else:
				if currmax == nums[start]:
					currmax = max(nums[start + 1:i + 1])
				if currmin == nums[start]:
					currmin = min(nums[start + 1:i + 1])
				start += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		left = 0
		n = len(nums)
		l = 0
		r = 1
		maxVal = nums[0]
		minVal = nums[0]
		res = 1
		while l < r and r < n:
			maxVal = max(maxVal, nums[r])
			minVal = min(minVal, nums[r])
			if maxVal - minVal <= limit:
				res = max(res, r - l + 1)
			else:
				if nums[l] == maxVal:
					maxVal = max(nums[l + 1:r + 1])
				if nums[l] == minVal:
					minVal = min(nums[l + 1:r + 1])
				l += 1
			r += 1
		return res
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_queue = collections.deque()
		min_queue = collections.deque()
		l = r = 0
		max_len = 0
		while r < len(nums):
			while max_queue and nums[r] >= max_queue[-1][0]:
				max_queue.pop()
			max_queue.append((nums[r], r))
			while min_queue and nums[r] <= min_queue[-1][0]:
				min_queue.pop()
			min_queue.append((nums[r], r))
			r += 1
			while max_queue[0][0] - min_queue[0][0] > limit:
				l += 1
				if max_queue[0][1] < l:
					max_queue.popleft()
				if min_queue[0][1] < l:
					min_queue.popleft()
			max_len = max(max_len, r - l)
		return max_len


from heapq import heappush, heapify, heappop

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(max_subsize, right, left) = (0, 0, 0)
		(max_vals, min_vals) = ([], [])
		heapify(max_vals)
		heapify(min_vals)
		while right < len(nums):
			diff = max_vals[0][0] * -1 - min_vals[0][0] if max_vals and min_vals else 0
			if diff <= limit:
				max_subsize = max(max_subsize, right - left)
				heappush(min_vals, (nums[right], right))
				heappush(max_vals, (nums[right] * -1, right))
				right += 1
			else:
				left += 1
				while max_vals and max_vals[0][1] < left:
					heappop(max_vals)
				while min_vals and min_vals[0][1] < left:
					heappop(min_vals)
			diff = max_vals[0][0] * -1 - min_vals[0][0] if max_vals and min_vals else 0
			if diff <= limit:
				max_subsize = max(max_subsize, right - left)
		return max_subsize


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minheap = []
		maxheap = []
		heapq.heapify(minheap)
		heapq.heapify(maxheap)
		length = 1
		i = 0
		j = 1
		heapq.heappush(minheap, [nums[0], 0])
		heapq.heappush(maxheap, [-nums[0], 0])
		while j < len(nums):
			if abs(minheap[0][0] - nums[j]) <= limit and abs(abs(maxheap[0][0]) - nums[j]) <= limit:
				length = max(length, j - i + 1)
				heapq.heappush(minheap, [nums[j], j])
				heapq.heappush(maxheap, [-nums[j], j])
				j = j + 1
			else:
				while len(minheap) > 0 and abs(minheap[0][0] - nums[j]) > limit:
					(ele, index) = heapq.heappop(minheap)
					i = max(i, index + 1)
				while len(maxheap) > 0 and abs(-maxheap[0][0] - nums[j]) > limit:
					(ele, index) = heapq.heappop(maxheap)
					i = max(i, index + 1)
				heapq.heappush(minheap, [nums[j], j])
				heapq.heappush(maxheap, [-nums[j], j])
				j = j + 1
		return length


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(p1, p2, ans, cnt, min_, max_) = (0, 0, 0, {nums[0]: 1}, nums[0], nums[0])
		while True:
			if max_ - min_ <= limit:
				ans = max(ans, p2 - p1 + 1)
				if p2 == len(nums) - 1:
					return ans
				p2 += 1
				if nums[p2] in cnt:
					cnt[nums[p2]] += 1
				else:
					cnt[nums[p2]] = 1
				max_ = max(max_, nums[p2])
				min_ = min(min_, nums[p2])
			else:
				num = nums[p1]
				p1 += 1
				if cnt[num] == 1:
					del cnt[num]
					if max_ == num:
						max_ = max(cnt.keys())
					if min_ == num:
						min_ = min(cnt.keys())
				else:
					cnt[num] -= 1


from collections import deque

class Solution:

	def longestSubarray(self, nums, limit):
		(res, last) = (0, -1)
		(maxQ, minQ) = (deque(), deque())
		for (i, val) in enumerate(nums):
			while maxQ and nums[maxQ[0]] - val > limit:
				last = max(last, maxQ.popleft())
			while maxQ and val >= nums[maxQ[-1]]:
				maxQ.pop()
			maxQ.append(i)
			while minQ and val - nums[minQ[0]] > limit:
				last = max(last, minQ.popleft())
			while minQ and val <= nums[minQ[-1]]:
				minQ.pop()
			minQ.append(i)
			res = max(res, i - last)
		return res

class Solution:

	def longestSubarray(self, A, limit):
		maxd = collections.deque()
		mind = collections.deque()
		i = 0
		for a in A:
			while len(maxd) and a > maxd[-1]:
				maxd.pop()
			while len(mind) and a < mind[-1]:
				mind.pop()
			maxd.append(a)
			mind.append(a)
			if maxd[0] - mind[0] > limit:
				if maxd[0] == A[i]:
					maxd.popleft()
				if mind[0] == A[i]:
					mind.popleft()
				i += 1
		return len(A) - i


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		if len(nums) == 1:
			return 1
		start = 0
		end = 1
		maxi = nums[0]
		mini = nums[0]
		max_l = 1
		while start <= end and end < len(nums):
			maxi = max(maxi, nums[end])
			mini = min(mini, nums[end])
			if maxi - mini <= limit:
				max_l = max(max_l, end - start + 1)
			else:
				if nums[start] == maxi:
					maxi = max(nums[start + 1:end + 1])
				if nums[start] == mini:
					mini = min(nums[start + 1:end + 1])
				start += 1
			end += 1
		return max_l


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		l = 0
		r = 1
		curr_max = nums[0]
		curr_min = nums[0]
		max_len = 1
		while l <= r and r < len(nums):
			curr_max = max(curr_max, nums[r])
			curr_min = min(curr_min, nums[r])
			if curr_max - curr_min <= limit:
				max_len = max(max_len, r - l + 1)
			else:
				if curr_max == nums[l]:
					curr_max = max(nums[l + 1:r + 1])
				if curr_min == nums[l]:
					curr_min = min(nums[l + 1:r + 1])
				l += 1
			r += 1
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_h = [(nums[0], 0)]
		max_h = [(-nums[0], 0)]
		heapq.heapify(min_h)
		heapq.heapify(max_h)
		(max_v, min_v) = (nums[0], nums[0])
		(l, r) = (0, 0)
		res = 1
		while r < len(nums):
			if max_v - min_v <= limit:
				r += 1
				if r < len(nums):
					heapq.heappush(min_h, (nums[r], r))
					heapq.heappush(max_h, (-nums[r], r))
					(max_v, min_v) = (-max_h[0][0], min_h[0][0])
			else:
				res = max(res, r - l)
				l += 1
				while min_h[0][1] < l:
					heapq.heappop(min_h)
				while max_h[0][1] < l:
					heapq.heappop(max_h)
			(max_v, min_v) = (-max_h[0][0], min_h[0][0])
		return max(res, r - l)


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_q = deque()
		min_q = deque()
		i = 0
		res = 0
		for (j, num) in enumerate(nums):
			while max_q and num > max_q[-1]:
				max_q.pop()
			while min_q and num < min_q[-1]:
				min_q.pop()
			max_q.append(num)
			min_q.append(num)
			while max_q[0] - min_q[0] > limit:
				if max_q[0] == nums[i]:
					max_q.popleft()
				if min_q[0] == nums[i]:
					min_q.popleft()
				i += 1
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		start = 0
		end = 0
		longest_size = 0
		maxa = nums[0]
		mina = nums[0]
		while end < len(nums):
			if maxa - mina <= limit:
				longest_size = max(longest_size, end - start)
				maxa = max(maxa, nums[end])
				mina = min(mina, nums[end])
				end += 1
			else:
				remove = nums[start]
				start += 1
				if remove == mina:
					while nums[start] <= mina:
						start += 1
					mina = min(nums[start:end + 1])
				if remove == maxa:
					while nums[start] >= maxa:
						start += 1
					maxa = max(nums[start:end + 1])
		if maxa - mina <= limit:
			longest_size = max(longest_size, end - start)
		return longest_size


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		max_stack = collections.deque([0])
		min_stack = collections.deque([0])
		(begin, end, longest) = (0, 0, 0)
		while end < n:
			while True:
				diff = nums[max_stack[0]] - nums[min_stack[0]]
				if diff > limit:
					if min_stack[0] == begin:
						min_stack.popleft()
					if max_stack[0] == begin:
						max_stack.popleft()
					begin += 1
				else:
					longest = max(longest, end - begin + 1)
					break
			end += 1
			if end < n:
				while min_stack and nums[end] <= nums[min_stack[-1]]:
					min_stack.pop()
				min_stack.append(end)
				while max_stack and nums[end] >= nums[max_stack[-1]]:
					max_stack.pop()
				max_stack.append(end)
		return longest


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums or len(nums) == 1:
			return len(nums)
		n = len(nums)
		i = 0
		j = 1
		res = 1
		min_in_window = nums[0]
		max_in_window = nums[0]
		while j < n:
			max_in_window = max(max_in_window, nums[j])
			min_in_window = min(min_in_window, nums[j])
			diff = abs(min_in_window - max_in_window)
			if diff <= limit:
				j += 1
				res = max(res, j - i)
			else:
				tmp = nums[i]
				while i <= j and i < n - 1 and (nums[i] == nums[i + 1]):
					i += 1
				if nums[i] == min_in_window:
					min_in_window = min(nums[i + 1:j + 1])
				if nums[i] == max_in_window:
					max_in_window = max(nums[i + 1:j + 1])
				i += 1
				j += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(max_len, start, end) = (1, 0, 0)
		(pqmin, pqmax) = ([], [])
		for end in range(len(nums)):
			heapq.heappush(pqmin, (nums[end], end))
			heapq.heappush(pqmax, (-nums[end], end))
			while start < end and abs(pqmax[0][0] + pqmin[0][0]) > limit:
				start += 1
				while pqmax and pqmax[0][1] < start:
					heapq.heappop(pqmax)
				while pqmin and pqmin[0][1] < start:
					heapq.heappop(pqmin)
			max_len = max(max_len, end - start + 1)
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		answer = 1
		counts = {nums[0]: 1}
		subarray = deque([nums[0]])
		max_val = nums[0]
		min_val = nums[0]
		for i in range(1, len(nums)):
			counts[nums[i]] = counts.get(nums[i], 0) + 1
			max_val = max(max_val, nums[i])
			min_val = min(min_val, nums[i])
			subarray.append(nums[i])
			if abs(max_val - min_val) > limit:
				while subarray:
					num = subarray.popleft()
					counts[num] -= 1
					if counts[num] == 0:
						if max_val == num:
							if subarray:
								max_val = max(subarray)
							else:
								max_val = 0
							break
						elif min_val == num:
							if subarray:
								min_val = min(subarray)
							else:
								min_val = 10 ** 9 + 1
							break
			answer = max(answer, len(subarray))
		return answer


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		i = 0
		j = 1
		n = len(nums)
		if n == 0:
			return 0
		mn = nums[0]
		mx = nums[0]
		l = 1
		while i <= j and j < n:
			if mn > nums[j]:
				mn = nums[j]
			if mx < nums[j]:
				mx = nums[j]
			if mx - mn <= limit:
				if j - i + 1 > l:
					l = j - i + 1
			else:
				if mn == nums[i]:
					mn = min(nums[i + 1:j + 1])
				if mx == nums[i]:
					mx = max(nums[i + 1:j + 1])
				i += 1
			j += 1
		return l


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxheap = []
		minheap = []
		start = 0
		maxlen = 0
		for (end, item) in enumerate(nums):
			heapq.heappush(minheap, (item, end))
			heapq.heappush(maxheap, (-item, end))
			while maxheap and minheap and (-maxheap[0][0] - minheap[0][0] > limit):
				start = min(maxheap[0][1], minheap[0][1]) + 1
				while maxheap[0][1] < start:
					heapq.heappop(maxheap)
				while minheap[0][1] < start:
					heapq.heappop(minheap)
			maxlen = max(maxlen, end - start + 1)
		return maxlen


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		res = 0
		(left, right) = (0, 0)
		(inc, dec) = (collections.deque(), collections.deque())
		while right < n:
			while inc and nums[inc[-1]] >= nums[right]:
				inc.pop()
			inc.append(right)
			while dec and nums[dec[-1]] <= nums[right]:
				dec.pop()
			dec.append(right)
			right += 1
			while nums[dec[0]] - nums[inc[0]] > limit:
				if inc[0] == left:
					inc.popleft()
				if dec[0] == left:
					dec.popleft()
				left += 1
			res = max(res, right - left)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(asc, desc) = (deque(), deque())
		left = 0
		longest = 0
		for (i, n) in enumerate(nums):
			if not asc:
				asc.append([n, i])
			else:
				while asc and asc[-1][0] > n:
					asc.pop()
				asc.append([n, i])
			if not desc:
				desc.append([n, i])
			else:
				while desc and desc[-1][0] < n:
					desc.pop()
				desc.append([n, i])
			while desc[0][0] - asc[0][0] > limit:
				if desc[0][1] < asc[0][1]:
					left = desc.popleft()[1] + 1
				else:
					left = asc.popleft()[1] + 1
			longest = max(longest, i - left + 1)
		return longest


class Solution:

	def longestSubarray(self, nums, limit):
		_min = _max = nums[0]
		count = 0
		(res, start) = (1, 0)
		for right in range(len(nums)):
			if _min > nums[right]:
				_min = nums[right]
			if _max < nums[right]:
				_max = nums[right]
			if _max - _min <= limit:
				count += 1
				if res < count:
					res = count
			else:
				_min = _max = nums[right]
				count = 1
				left = right - 1
				while left >= start and abs(_max - nums[left]) <= limit and (abs(_min - nums[left]) <= limit):
					if _min > nums[left]:
						_min = nums[left]
					if _max < nums[left]:
						_max = nums[left]
					count += 1
					left -= 1
				start = right + 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		l = r = 0
		minq = collections.deque()
		maxq = collections.deque()
		ans = 0
		while r < len(nums):
			while minq and nums[minq[-1]] >= nums[r]:
				minq.pop()
			while maxq and nums[maxq[-1]] <= nums[r]:
				maxq.pop()
			minq.append(r)
			maxq.append(r)
			while nums[maxq[0]] - nums[minq[0]] > limit:
				l += 1
				if l > minq[0]:
					minq.popleft()
				if l > maxq[0]:
					maxq.popleft()
			ans = max(ans, r - l + 1)
			r += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 1:
			return 1
		maxL = 0
		beg = 0
		(minQueue, maxQueue) = (collections.deque([]), collections.deque([]))
		end = beg
		while end < len(nums):
			while len(minQueue) > 0 and nums[end] < minQueue[-1]:
				minQueue.pop()
			minQueue.append(nums[end])
			while len(maxQueue) > 0 and nums[end] > maxQueue[-1]:
				maxQueue.pop()
			maxQueue.append(nums[end])
			if maxQueue[0] - minQueue[0] <= limit:
				maxL = max(maxL, end - beg + 1)
			else:
				if maxQueue[0] == nums[beg]:
					maxQueue.popleft()
				if minQueue[0] == nums[beg]:
					minQueue.popleft()
				beg += 1
			end += 1
		return maxL


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_deque = collections.deque()
		max_deque = collections.deque()
		left = 0
		right = 0
		max_size = 0
		while right < len(nums):
			while min_deque and nums[min_deque[-1]] >= nums[right]:
				min_deque.pop()
			while max_deque and nums[max_deque[-1]] <= nums[right]:
				max_deque.pop()
			min_deque.append(right)
			max_deque.append(right)
			while nums[max_deque[0]] - nums[min_deque[0]] > limit:
				left += 1
				if max_deque[0] < left:
					max_deque.popleft()
				if min_deque[0] < left:
					min_deque.popleft()
			right += 1
			max_size = max(max_size, right - left)
		return max_size


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxq, minq) = ([], [])
		res = i = 0
		for j in range(len(nums)):
			heapq.heappush(maxq, (-nums[j], j))
			heapq.heappush(minq, (nums[j], j))
			while -maxq[0][0] - minq[0][0] > limit:
				i = min(maxq[0][1], minq[0][1]) + 1
				while i > maxq[0][1]:
					heapq.heappop(maxq)
				while i > minq[0][1]:
					heapq.heappop(minq)
			res = max(res, j - i + 1)
		return res


from heapq import heappush, heappop

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		i = j = best = 0
		(minHeap, maxHeap) = ([], [])
		while j < len(nums):
			heappush(minHeap, (nums[j], j))
			heappush(maxHeap, (-nums[j], j))
			while abs(nums[j] + maxHeap[0][0]) > limit:
				i = max(i, heappop(maxHeap)[1] + 1)
			while abs(nums[j] - minHeap[0][0]) > limit:
				i = max(i, heappop(minHeap)[1] + 1)
			j += 1
			best = max(best, j - i)
		return best


import collections

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minq = collections.deque()
		maxq = collections.deque()
		j = 0
		count = 0
		for (i, val) in enumerate(nums):
			while len(minq) > 0 and minq[-1] > val:
				minq.pop()
			while len(maxq) > 0 and maxq[-1] < val:
				maxq.pop()
			minq.append(val)
			maxq.append(val)
			while len(minq) > 0 and len(maxq) > 0 and (maxq[0] - minq[0] > limit):
				if nums[j] == maxq[0]:
					maxq.popleft()
				if nums[j] == minq[0]:
					minq.popleft()
				j += 1
			count = max(count, i - j + 1)
		return count


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums or limit < 0:
			return 0
		anchor = ans = 0
		(hi, lo) = (float('-inf'), float('inf'))
		for i in range(len(nums)):
			hi = max(hi, nums[i])
			lo = min(lo, nums[i])
			if hi - lo <= limit:
				ans = max(ans, i - anchor + 1)
			else:
				if nums[anchor] == hi:
					hi = max(nums[anchor + 1:i + 1])
				elif nums[anchor] == lo:
					lo = min(nums[anchor + 1:i + 1])
				anchor += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		if len(nums) == 1:
			return 1
		l = 0
		r = 1
		cur_mx = nums[0]
		cur_mn = nums[0]
		max_l = 1
		while l <= r and r < len(nums):
			cur_mx = max(cur_mx, nums[r])
			cur_mn = min(cur_mn, nums[r])
			if cur_mx - cur_mn <= limit:
				max_l = max(max_l, r - l + 1)
			else:
				if nums[l] == cur_mx:
					cur_mx = max(nums[l + 1:r + 1])
				if nums[l] == cur_mn:
					cur_mn = min(nums[l + 1:r + 1])
				l += 1
			r += 1
		return max_l


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minheap = [[nums[0], 0]]
		maxheap = [[-nums[0], 0]]
		left = -1
		res = 1
		for (i, val) in enumerate(nums[1:]):
			j = i + 1
			while len(maxheap) and len(minheap) and (max(val, -maxheap[0][0]) - min(val, minheap[0][0]) > limit):
				if val == max(val, -maxheap[0][0]):
					(v, l) = heapq.heappop(minheap)
				if minheap and val == min(val, minheap[0][0]):
					(v, l) = heapq.heappop(maxheap)
				left = max(l, left)
			res = max(j - left, res)
			heapq.heappush(minheap, [val, j])
			heapq.heappush(maxheap, [-val, j])
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxLen = 1
		curMax = curMin = nums[0]
		l = r = 0
		while r < len(nums):
			curMax = max(curMax, nums[r])
			curMin = min(curMin, nums[r])
			if curMax - curMin <= limit:
				maxLen = max(maxLen, r - l + 1)
			else:
				if nums[l] == curMin:
					curMin = min(nums[l + 1:r + 1])
				if nums[l] == curMax:
					curMax = max(nums[l + 1:r + 1])
				l += 1
			r += 1
		return maxLen


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(max_q, min_q) = ([[nums[0], 0]], [[nums[0], 0]])
		ans = 1
		i = j = 0
		while j < len(nums):
			heapq.heappush(max_q, [-nums[j], j])
			heapq.heappush(min_q, [nums[j], j])
			if -max_q[0][0] - min_q[0][0] <= limit:
				ans = max(ans, j - i + 1)
				j += 1
			else:
				i = min(max_q[0][1], min_q[0][1]) + 1
				while max_q[0][1] < i:
					heapq.heappop(max_q)
				while min_q[0][1] < i:
					heapq.heappop(min_q)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		if n == 0:
			return 0
		if n == 1:
			return 1
		ans = 1
		minelement = maxelement = nums[0]
		l = 0
		r = 1
		while r < n and l <= r:
			minelement = min(minelement, nums[r])
			maxelement = max(maxelement, nums[r])
			if maxelement - minelement <= limit:
				ans = max(ans, r - l + 1)
			else:
				if minelement == nums[l]:
					minelement = min(nums[l + 1:r + 1])
				if maxelement == nums[l]:
					maxelement = max(nums[l + 1:r + 1])
				l += 1
			r += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 0:
			return 0
		if len(nums) == 1:
			return 1
		ans = 1
		minNum = nums[0]
		maxNum = nums[0]
		i = 0
		j = 0
		n = len(nums)
		while i < n and j < n:
			maxNum = max(maxNum, nums[i])
			minNum = min(minNum, nums[i])
			if abs(maxNum - minNum) > limit:
				if nums[j] == maxNum:
					maxNum = max(nums[j + 1:i + 1])
				elif nums[j] == minNum:
					minNum = min(nums[j + 1:i + 1])
				j += 1
			else:
				ans = max(ans, i - j + 1)
			i += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		(l, r) = (0, 0)
		n = len(nums)
		ll = 0
		mmin = nums[0]
		mmax = nums[0]
		while l <= r and r < n:
			mmax = max(mmax, nums[r])
			mmin = min(mmin, nums[r])
			if abs(mmax - mmin) <= limit:
				ll = max(ll, r - l + 1)
			else:
				if nums[l] == mmax:
					mmax = max(nums[l + 1:r + 1])
				if nums[l] == mmin:
					mmin = min(nums[l + 1:r + 1])
				l += 1
			r += 1
		return ll


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		smallest = largest = nums[0]
		(start, end, window) = (0, 1, 1)
		while end < len(nums):
			(smallest, largest) = (min(smallest, nums[end]), max(largest, nums[end]))
			if largest - smallest <= limit:
				window = max(window, end - start + 1)
			else:
				if nums[start] == smallest:
					smallest = min(nums[start + 1:end + 1])
				if nums[start] == largest:
					largest = max(nums[start + 1:end + 1])
				start += 1
			end += 1
		return window


import collections

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_deque = collections.deque()
		max_deque = collections.deque()
		longest_subarray = 0
		(i, j) = (0, 0)
		min_deque.append((nums[0], 0))
		max_deque.append((-nums[0], 0))
		while j < len(nums) and len(nums) - i + 1 > longest_subarray:
			while min_deque and min_deque[0][1] < i:
				min_deque.popleft()
			while max_deque and max_deque[0][1] < i:
				max_deque.popleft()
			while i > j or (j < len(nums) - 1 and max(-max_deque[0][0], nums[j + 1]) - min(min_deque[0][0], nums[j + 1]) <= limit):
				j += 1
				self.insert_to_deque(min_deque, nums[j], j)
				self.insert_to_deque(max_deque, -nums[j], j)
			longest_subarray = max(longest_subarray, j - i + 1)
			i += 1
		return longest_subarray

	def insert_to_deque(self, deque_object, value, index):
		while len(deque_object) > 0 and deque_object[-1][0] >= value:
			deque_object.pop()
		deque_object.append((value, index))


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		currMax = nums[0]
		currMin = nums[0]
		maxSize = 1
		beg = 0
		end = 0
		while end < len(nums):
			currMax = max(currMax, nums[end])
			currMin = min(currMin, nums[end])
			if currMax - currMin > limit:
				beg += 1
				if currMax == nums[beg - 1]:
					while currMax == nums[beg]:
						beg += 1
					currMax = max(nums[beg:end + 1])
				if currMin == nums[beg - 1]:
					while currMin == nums[beg]:
						beg += 1
					currMin = min(nums[beg:end + 1])
			else:
				end += 1
			maxSize = max(maxSize, end - beg)
		return maxSize


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		(min_heap, max_heap) = ([], [])
		(res, i) = (0, 0)
		for (j, num) in enumerate(nums):
			heapq.heappush(min_heap, [num, j])
			heapq.heappush(max_heap, [-num, j])
			while abs(min_heap[0][0] + max_heap[0][0]) > limit:
				i = min(min_heap[0][1], max_heap[0][1]) + 1
				while min_heap[0][1] < i:
					heapq.heappop(min_heap)
				while max_heap[0][1] < i:
					heapq.heappop(max_heap)
			res = max(res, j - i + 1)
		return res


from heapq import heappush, heappop
from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		left = 0
		min_q = deque()
		max_q = deque()
		longest = 0
		for (right, number) in enumerate(nums):
			_index = right
			while max_q and number > max_q[-1][0]:
				(_, _index) = max_q.pop()
			max_q.append((number, _index))
			_index = right
			while min_q and number <= min_q[-1][0]:
				(_, _index) = min_q.pop()
			min_q.append((number, _index))
			while max_q[0][0] - min_q[0][0] > limit:
				if max_q[0][1] > min_q[0][1]:
					if len(min_q) == 1:
						q = max_q
					else:
						q = min_q
				elif len(max_q) == 1:
					q = min_q
				else:
					q = max_q
				(_, _index) = q.popleft()
			left = max(min_q[0][1], max_q[0][1])
			longest = max(longest, right - left + 1)
		return longest

	def calc_diff(self, a, b):
		return abs(a - b)


class Solution:

	def longestSubarray(self, nums, limit):
		(max_h, min_h) = ([], [])
		res = l = 0
		for (r, num) in enumerate(nums):
			heapq.heappush(max_h, (-num, r))
			heapq.heappush(min_h, (num, r))
			while -max_h[0][0] - min_h[0][0] > limit:
				l += 1
				while max_h[0][1] < l:
					heapq.heappop(max_h)
				while min_h[0][1] < l:
					heapq.heappop(min_h)
			res = max(res, r - l + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if limit < 0:
			return 0
		(i, j) = (0, 1)
		res = 0
		(max_q, min_q) = (collections.deque(), collections.deque())
		max_q.append((0, nums[0]))
		min_q.append((0, nums[0]))
		while j < len(nums):
			if max_q[0][1] - min_q[0][1] <= limit:
				while max_q and nums[j] > max_q[-1][1]:
					max_q.pop()
				while min_q and nums[j] < min_q[-1][1]:
					min_q.pop()
				max_q.append((j, nums[j]))
				min_q.append((j, nums[j]))
				j += 1
			if max_q[0][1] - min_q[0][1] > limit:
				res = j - i - 1 if j - i - 1 > res else res
				(min_i, max_i) = (min_q[0][0], max_q[0][0])
				if min_i < max_i:
					i = min_i + 1
					min_q.popleft()
				else:
					i = max_i + 1
					max_q.popleft()
		return j - i if j - i > res else res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:

		def helper(arr, limit):
			from collections import deque
			Q = deque()
			Q_2 = deque()
			result = 0
			if len(nums) == 1:
				return 1
			for i in range(len(arr)):
				v = arr[i]
				while len(Q) and abs(v - Q[0][1]) > limit:
					(j, _) = Q.popleft()
				while len(Q_2) and abs(v - Q_2[0][1]) > limit:
					(j, _) = Q_2.popleft()
				if len(Q) and len(Q_2):
					r = i - max(Q[0][0], Q_2[0][0]) + 1
					result = max(result, r)
				ni = i
				while len(Q) and v <= Q[-1][1]:
					(mp, vp) = Q.pop()
					if abs(vp - v) <= limit:
						ni = mp
				Q.append((ni, v))
				ni = i
				while len(Q_2) and v >= Q_2[-1][1]:
					(mp, vp) = Q_2.pop()
					if abs(vp - v) <= limit:
						ni = mp
				Q_2.append((ni, v))
			return result
		r1 = helper(nums, limit)
		return r1


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		pre = 0
		res = 1
		maxs = []
		mins = []
		for i in range(len(nums)):
			while maxs and maxs[-1] < nums[i]:
				maxs.pop()
			while mins and mins[-1] > nums[i]:
				mins.pop()
			maxs.append(nums[i])
			mins.append(nums[i])
			while maxs[0] - mins[0] > limit:
				if maxs[0] == nums[pre]:
					maxs.pop(0)
				if mins[0] == nums[pre]:
					mins.pop(0)
				pre += 1
			res = max(res, i - pre + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		ans = 1
		st = en = 0
		min_q = collections.deque()
		max_q = collections.deque()
		while en < len(nums):
			while min_q and nums[en] <= nums[min_q[-1]]:
				min_q.pop()
			while max_q and nums[en] >= nums[max_q[-1]]:
				max_q.pop()
			min_q.append(en)
			max_q.append(en)
			while nums[max_q[0]] - nums[min_q[0]] > limit:
				st += 1
				if st > min_q[0]:
					min_q.popleft()
				if st > max_q[0]:
					max_q.popleft()
			ans = max(ans, en - st + 1)
			en += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_deque = collections.deque()
		max_deque = collections.deque()
		l = 0
		ans = 0
		for (r, num) in enumerate(nums):
			while min_deque and nums[min_deque[-1]] >= num:
				min_deque.pop()
			while max_deque and nums[max_deque[-1]] <= num:
				max_deque.pop()
			min_deque.append(r)
			max_deque.append(r)
			while nums[max_deque[0]] - nums[min_deque[0]] > limit:
				l += 1
				while max_deque[0] < l:
					max_deque.popleft()
				while min_deque[0] < l:
					min_deque.popleft()
			ans = max(ans, r - l + 1)
		return ans


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		longest = 0
		minHeap = []
		maxHeap = []
		front = -1
		back = 0
		while back < len(nums):
			needsShrinking = False
			if front < len(nums) - 1:
				front += 1
				heapq.heappush(minHeap, (nums[front], front))
				heapq.heappush(maxHeap, (-nums[front], front))
			else:
				needsShrinking = True
			while needsShrinking or (minHeap and maxHeap and (abs(minHeap[0][0] + maxHeap[0][0]) > limit)):
				needsShrinking = False
				back += 1
				while minHeap and minHeap[0][1] < back:
					heapq.heappop(minHeap)
				while maxHeap and maxHeap[0][1] < back:
					heapq.heappop(maxHeap)
			longest = max(longest, front - back + 1)
		return longest


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(ret, vals) = (0, SortedList())
		(l, r, n) = (0, 0, len(nums))
		while r < n:
			vals.add(nums[r])
			while vals[-1] - vals[0] > limit:
				vals.remove(nums[l])
				l += 1
			r += 1
			ret = max(ret, r - l)
		return ret


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minhp = []
		maxhp = []
		i = 0
		ans = 0
		for (j, el) in enumerate(nums):
			heapq.heappush(minhp, [el, j])
			heapq.heappush(maxhp, [-el, j])
			while -maxhp[0][0] - minhp[0][0] > limit:
				i = min(maxhp[0][1], minhp[0][1]) + 1
				while maxhp[0][1] < i:
					heapq.heappop(maxhp)
				while minhp[0][1] < i:
					heapq.heappop(minhp)
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxd = []
		mind = []
		left = 0
		sol = 1
		for (i, num) in enumerate(nums):
			while maxd and nums[maxd[-1]] < num:
				maxd.pop()
			while mind and nums[mind[-1]] > num:
				mind.pop()
			maxd.append(i)
			mind.append(i)
			while nums[maxd[0]] - nums[mind[0]] > limit:
				if nums[maxd[0]] == nums[left]:
					maxd.pop(0)
				if nums[mind[0]] == nums[left]:
					mind.pop(0)
				left += 1
			sol = max(sol, i - left + 1)
		return sol


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(mxh, mnh) = ([], [])
		i = j = 0
		ans = 0
		while i < len(nums):
			if j < len(nums) and (not mxh or not mnh or abs(mxh[0][0] + mnh[0][0]) <= limit):
				heappush(mnh, [nums[j], j])
				heappush(mxh, [-nums[j], j])
				j += 1
			else:
				if not mxh or not mnh or abs(mxh[0][0] + mnh[0][0]) <= limit:
					ans = max(ans, j - i)
				else:
					ans = max(ans, j - i - 1)
				i += 1
				while mxh and mxh[0][1] < i:
					heappop(mxh)
				while mnh and mnh[0][1] < i:
					heappop(mnh)
		return ans


from collections import deque

class MinQ:

	def __init__(self):
		self.Q = collections.deque([])

	def append(self, num):
		cnt = 0
		while self.Q and self.Q[-1][0] >= num:
			cnt += self.Q.pop()[1] + 1
		self.Q.append([num, cnt])

	def popleft(self):
		if not self.Q:
			return None
		if self.Q[0][1] == 0:
			self.Q.popleft()
		else:
			self.Q[0][1] -= 1

	@property
	def minv(self):
		return self.Q[0][0]

class MaxQ:

	def __init__(self):
		self.Q = collections.deque([])

	def append(self, num):
		cnt = 0
		while self.Q and self.Q[-1][0] <= num:
			cnt += self.Q.pop()[1] + 1
		self.Q.append([num, cnt])

	def popleft(self):
		if not self.Q:
			return None
		if self.Q[0][1] == 0:
			self.Q.popleft()
		else:
			self.Q[0][1] -= 1

	@property
	def maxv(self):
		return self.Q[0][0]

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		left = 0
		res = 0
		right = 0
		maxq = MaxQ()
		minq = MinQ()
		while right < n:
			maxq.append(nums[right])
			minq.append(nums[right])
			while maxq.maxv - minq.minv > limit:
				maxq.popleft()
				minq.popleft()
				left += 1
			res = max(right - left + 1, res)
			right += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(max_heap, min_heap) = ([], [])
		max_len = 0
		l = 0
		for (r, n) in enumerate(nums):
			heapq.heappush(max_heap, (-n, r))
			heapq.heappush(min_heap, (n, r))
			while -max_heap[0][0] - min_heap[0][0] > limit:
				l = min(max_heap[0][1], min_heap[0][1]) + 1
				while max_heap[0][1] < l:
					heapq.heappop(max_heap)
				while min_heap[0][1] < l:
					heapq.heappop(min_heap)
			max_len = max(max_len, r - l + 1)
		return max_len


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		sl = SortedList()
		start = 0
		ans = 0
		for end in range(len(nums)):
			x = nums[end]
			sl.add(x)
			while sl[-1] - sl[0] > limit and start <= end:
				sl.remove(nums[start])
				start += 1
			if start <= end:
				ans = max(ans, end - start + 1)
		return ans


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_heap = []
		max_heap = []
		(i, j) = (0, 0)
		res = 0
		while i < len(nums) and j < len(nums):
			heapq.heappush(min_heap, (nums[j], j))
			heapq.heappush(max_heap, (-nums[j], j))
			while -max_heap[0][0] - min_heap[0][0] > limit:
				i = min(i, min_heap[0][1], max_heap[0][1]) + 1
				while max_heap[0][1] < i:
					heapq.heappop(max_heap)
				while min_heap[0][1] < i:
					heapq.heappop(min_heap)
			res = max(res, j - i + 1)
			j += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxs, mins) = ([], [])
		res = 0
		start = 0
		for (i, n) in enumerate(nums):
			while maxs and maxs[-1] < n:
				maxs.pop()
			while mins and mins[-1] > n:
				mins.pop()
			maxs.append(n)
			mins.append(n)
			while maxs[0] - mins[0] > limit:
				if maxs[0] == nums[start]:
					maxs.pop(0)
				if mins[0] == nums[start]:
					mins.pop(0)
				start += 1
			res = max(res, i - start + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 0:
			return 0
		if len(nums) == 1:
			return 1
		maxStack = []
		minStack = []
		result = 1
		leftPos = 0
		for i in range(0, len(nums)):
			while maxStack and nums[i] < nums[maxStack[0]] - limit:
				leftPos = max(leftPos, maxStack.pop(0) + 1)
			while minStack and nums[i] > nums[minStack[0]] + limit:
				leftPos = max(leftPos, minStack.pop(0) + 1)
			length = i - leftPos + 1
			if length > result:
				result = length
			while maxStack and nums[i] > nums[maxStack[-1]]:
				maxStack.pop()
			maxStack.append(i)
			while minStack and nums[i] < nums[minStack[-1]]:
				minStack.pop()
			minStack.append(i)
		return result


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		sl = SortedList([])
		(st, end, res) = (0, 0, 0)
		for val in nums:
			sl.add(val)
			end += 1
			while abs(sl[0] - sl[-1]) > limit:
				sl.remove(nums[st])
				st += 1
			res = max(res, end - st)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_deque = collections.deque()
		min_deque = collections.deque()
		start = 0
		end = 0
		max_limit_subarray = 0
		for end in range(len(nums)):
			while min_deque and nums[end] < nums[min_deque[-1]]:
				min_deque.pop()
			min_deque.append(end)
			while max_deque and nums[end] > nums[max_deque[-1]]:
				max_deque.pop()
			max_deque.append(end)
			while abs(nums[max_deque[0]] - nums[min_deque[0]]) > limit:
				start += 1
				if start > min_deque[0]:
					min_deque.popleft()
				if start > max_deque[0]:
					max_deque.popleft()
			max_limit_subarray = max(max_limit_subarray, end - start + 1)
		return max_limit_subarray


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		i = 0
		j = 0
		n = len(nums)
		maxq = []
		minq = []
		max_l = 0
		while i < n and j < n:
			while maxq and nums[j] > maxq[-1]:
				maxq.pop()
			while minq and nums[j] < minq[-1]:
				minq.pop()
			maxq.append(nums[j])
			minq.append(nums[j])
			while maxq[0] - minq[0] > limit:
				if nums[i] == maxq[0]:
					maxq.pop(0)
				if nums[i] == minq[0]:
					minq.pop(0)
				i += 1
			max_l = max(max_l, j - i + 1)
			j += 1
		return max_l


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		maxs = []
		mins = []
		l = res = 0
		for r in range(n):
			while maxs and maxs[-1] < nums[r]:
				maxs.pop()
			maxs.append(nums[r])
			while mins and mins[-1] > nums[r]:
				mins.pop()
			mins.append(nums[r])
			while maxs[0] - mins[0] > limit:
				if maxs[0] == nums[l]:
					maxs.pop(0)
				if mins[0] == nums[l]:
					mins.pop(0)
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(mx, mi) = ([0], [0])
		res = 1
		left = 0
		for c in range(1, len(nums)):
			num = nums[c]
			while mx and nums[mx[-1]] < num:
				mx.pop()
			mx.append(c)
			while mi and nums[mi[-1]] > num:
				mi.pop()
			mi.append(c)
			while mi and mx and (nums[mx[0]] - nums[mi[0]] > limit):
				left += 1
				if left > mx[0]:
					mx.pop(0)
				if left > mi[0]:
					mi.pop(0)
			res = max(res, c - left + 1)
		return res


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		s = SortedList()
		max_length = 0
		j = 0
		for i in range(len(nums)):
			s.add(nums[i])
			while s and s[-1] - s[0] > limit:
				s.remove(nums[j])
				j += 1
			max_length = max(max_length, i - j + 1)
		return max_length


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		result = 0
		min_deque = []
		max_deque = []
		start = 0
		for (index, value) in enumerate(nums):
			while len(min_deque) and value < min_deque[-1]:
				min_deque.pop()
			while len(max_deque) and value > max_deque[-1]:
				max_deque.pop()
			min_deque.append(value)
			max_deque.append(value)
			while max_deque[0] - min_deque[0] > limit:
				if nums[start] == min_deque[0]:
					min_deque.pop(0)
				if nums[start] == max_deque[0]:
					max_deque.pop(0)
				start += 1
			result = max(result, index - start + 1)
		return result


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		from collections import deque
		n = len(nums)
		(l, r) = (0, -1)
		(max_window, min_window) = (deque(), deque())
		while r < n - 1:
			r += 1
			while max_window and max_window[-1] < nums[r]:
				max_window.pop()
			while min_window and min_window[-1] > nums[r]:
				min_window.pop()
			max_window.append(nums[r])
			min_window.append(nums[r])
			if max_window[0] - min_window[0] > limit:
				if max_window[0] == nums[l]:
					max_window.popleft()
				if min_window[0] == nums[l]:
					min_window.popleft()
				l += 1
		return r - l + 1


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		from sortedcontainers import SortedList
		wd = SortedList([nums[0]])
		max_len = 1
		l = 0
		r = 0
		while r < len(nums):
			minn = wd[0]
			maxx = wd[-1]
			if maxx - minn <= limit:
				max_len = max(max_len, r - l + 1)
				r += 1
				if r < len(nums):
					wd.add(nums[r])
			else:
				wd.discard(nums[l])
				l += 1
		return max_len


from typing import List
from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(i, j) = (0, 0)
		maxLen = 1
		sortedInterval = SortedList([nums[0]])
		while i <= j < len(nums):
			(minVal, maxVal) = (sortedInterval[0], sortedInterval[-1])
			if maxVal - minVal <= limit:
				maxLen = max(j - i + 1, maxLen)
				j += 1
				if j < len(nums):
					sortedInterval.add(nums[j])
			elif i < j:
				sortedInterval.discard(nums[i])
				i += 1
			else:
				j += 1
				i = j
		return maxLen


def add_to_max_heap(heap, value):
	heapq.heappush(heap, value)

def add_to_min_heap(heap, value):
	heapq.heappush(heap, value)

def get_max_val(heap):
	return heap[0][0]

def get_min_val(heap):
	return heap[0][0]

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		l = 0
		r = 0
		ans = 0
		max_heap = []
		min_heap = []
		while l < len(nums) and r < len(nums):
			add_to_max_heap(max_heap, (-nums[r], r))
			add_to_min_heap(min_heap, (nums[r], r))
			max_val = -get_max_val(max_heap)
			min_val = get_min_val(min_heap)
			if abs(max_val - min_val) <= limit:
				ans = max(ans, r - l + 1)
				r += 1
			else:
				while min_heap and min_heap[0][1] < l + 1:
					heapq.heappop(min_heap)
				while max_heap and max_heap[0][1] < l + 1:
					heapq.heappop(max_heap)
				l += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_heap = []
		max_heap = []
		longest_window = 1
		min_idx = 0
		for (i, num) in enumerate(nums):
			heapq.heappush(min_heap, (num, i))
			heapq.heappush(max_heap, (-num, i))
			while min_heap[0][1] < min_idx:
				heapq.heappop(min_heap)
			while max_heap[0][1] < min_idx:
				heapq.heappop(max_heap)
			if abs(min_heap[0][0] + max_heap[0][0]) > limit:
				if min_heap[0][1] < max_heap[0][1]:
					min_idx = min_heap[0][1] + 1
					heapq.heappop(min_heap)
				else:
					min_idx = max_heap[0][1] + 1
					heapq.heappop(max_heap)
			longest_window = max(longest_window, i - min_idx + 1)
		return longest_window


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		rlt = 1
		q = collections.deque([nums[0]])
		(max_stack, min_stack) = ([nums[0]], [nums[0]])
		for i in range(1, len(nums)):
			while max_stack and (max_stack[0] - nums[i] > limit or nums[i] - min_stack[0] > limit):
				head = q.popleft()
				if head == max_stack[0]:
					max_stack.pop(0)
				if head == min_stack[0]:
					min_stack.pop(0)
			q.append(nums[i])
			while max_stack and max_stack[-1] < nums[i]:
				max_stack.pop()
			while min_stack and min_stack[-1] > nums[i]:
				min_stack.pop()
			max_stack.append(nums[i])
			min_stack.append(nums[i])
			rlt = max(rlt, len(q))
		return rlt


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not len(nums):
			return 0
		output = 1
		s_idx = 0
		e_idx = 0
		pqmin = []
		pqmax = []
		for e_idx in range(len(nums)):
			heapq.heappush(pqmin, (nums[e_idx], e_idx))
			heapq.heappush(pqmax, (-nums[e_idx], e_idx))
			while s_idx < e_idx and abs(pqmax[0][0] + pqmin[0][0]) > limit:
				s_idx += 1
				while pqmax and pqmax[0][1] < s_idx:
					heapq.heappop(pqmax)
				while pqmin and pqmin[0][1] < s_idx:
					heapq.heappop(pqmin)
			output = max(output, e_idx - s_idx + 1)
		return output


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		winMax = [0]
		winMin = [0]
		i = j = 0
		res = 0
		while i < len(nums) - 1 and j < len(nums) - 1:
			diff = nums[winMax[0]] - nums[winMin[0]]
			if diff <= limit:
				res = max(res, j - i + 1)
			if diff <= limit:
				j += 1
				while winMax and nums[j] > nums[winMax[-1]]:
					winMax.pop(-1)
				winMax.append(j)
				while winMin and nums[j] < nums[winMin[-1]]:
					winMin.pop(-1)
				winMin.append(j)
			else:
				if i == winMax[0]:
					winMax.pop(0)
				if i == winMin[0]:
					winMin.pop(0)
				i += 1
		diff = nums[winMax[0]] - nums[winMin[0]]
		if diff <= limit:
			res = max(res, j - i + 1)
		return res


import bisect

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if limit < 0:
			return 0
		n = len(nums)
		if n < 2:
			return n
		longest = 1
		(l, r) = (0, 0)
		window = []
		while l < n and r < n:
			if not window:
				window.append(nums[r])
				r += 1
			else:
				curr = nums[r]
				(minimum, maximum) = (window[0], window[-1])
				if abs(curr - minimum) <= limit and abs(curr - maximum) <= limit:
					bisect.insort(window, curr)
					r += 1
					longest = max(longest, r - l)
				else:
					window.remove(nums[l])
					l += 1
		return longest


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(max_q, min_q) = ([], [])
		ans = 1
		l = 0
		for (i, num) in enumerate(nums):
			while len(max_q) and nums[max_q[-1]] < num:
				max_q.pop(-1)
			while len(min_q) and nums[min_q[-1]] > num:
				min_q.pop(-1)
			min_q.append(i)
			max_q.append(i)
			while nums[max_q[0]] - nums[min_q[0]] > limit:
				if max_q[0] > min_q[0]:
					l = min_q.pop(0) + 1
				else:
					l = max_q.pop(0) + 1
			ans = max(i - l + 1, ans)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		incr_q = [nums[0]]
		decr_q = [nums[0]]
		res = 1
		left = 0
		right = 1
		while right < len(nums):
			while incr_q and incr_q[-1] > nums[right]:
				incr_q.pop()
			incr_q.append(nums[right])
			while decr_q and decr_q[-1] < nums[right]:
				decr_q.pop()
			decr_q.append(nums[right])
			while incr_q and decr_q and (decr_q[0] - incr_q[0] > limit):
				if nums[left] == incr_q[0]:
					incr_q.pop(0)
				if nums[left] == decr_q[0]:
					decr_q.pop(0)
				left += 1
			res = max(right - left + 1, res)
			right += 1
		return res


from heapq import heappush, heappop

class Solution:

	def longestSubarray(self, nums, limit):
		discard = -1
		res = 0
		(minq, maxq) = ([], [])
		for i in range(len(nums)):
			while minq and abs(nums[i] - minq[0][0]) > limit:
				(_, index) = heappop(minq)
				discard = max(discard, index)
			heappush(minq, (nums[i], i))
			while maxq and abs(nums[i] + maxq[0][0]) > limit:
				(_, index) = heappop(maxq)
				discard = max(discard, index)
			heappush(maxq, (-nums[i], i))
			res = max(res, i - discard)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 0:
			return 0
		if len(nums) == 1:
			return 1
		left = 0
		right = 1
		cur_max = cur_min = nums[0]
		max_len = 1
		while right < len(nums):
			cur_max = max(cur_max, nums[right])
			cur_min = min(cur_min, nums[right])
			if cur_max - cur_min <= limit:
				max_len = max(max_len, right - left + 1)
			else:
				if nums[left] == cur_max:
					cur_max = max(nums[left + 1:right + 1])
				if nums[left] == cur_min:
					cur_min = min(nums[left + 1:right + 1])
				left += 1
			right += 1
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		left = 0
		right = 1
		ans = 1
		currMax = nums[0]
		currMin = nums[0]
		while left <= right and right < len(nums):
			currMax = max(currMax, nums[right])
			currMin = min(currMin, nums[right])
			if currMax - currMin <= limit:
				ans = max(ans, right - left + 1)
			else:
				if nums[left] == currMax:
					currMax = max(nums[left + 1:right + 1])
				if nums[left] == currMin:
					currMin = min(nums[left + 1:right + 1])
				left += 1
			right += 1
		return ans


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		s = SortedList()
		j = ans = 0
		for (i, val) in enumerate(nums):
			s.add(val)
			while s and s[-1] - s[0] > limit:
				s.remove(nums[j])
				j += 1
			ans = max(ans, i - j + 1)
		return ans


from bisect import insort

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		win = []
		n = len(nums)
		i = j = 0
		max_len = 0
		while j < n:
			if not win:
				win.append(nums[j])
			else:
				insort(win, nums[j])
			while win[-1] - win[0] > limit:
				win.remove(nums[i])
				i += 1
			if j - i + 1 > max_len:
				max_len = j - i + 1
			j += 1
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 0:
			return 0
		dec_stack = []
		inc_stack = []
		max_interval = 1
		(l, r) = (0, 0)
		(min_v, max_v) = (nums[0], nums[0])
		dec_stack.append((nums[0], 0))
		inc_stack.append((nums[0], 0))
		while l < len(nums) and r < len(nums):
			while max_v - min_v <= limit:
				max_interval = max(max_interval, r - l + 1)
				r += 1
				if r == len(nums):
					break
				while dec_stack and nums[r] > dec_stack[-1][0]:
					dec_stack.pop(-1)
				dec_stack.append((nums[r], r))
				max_v = dec_stack[0][0]
				while inc_stack and nums[r] < inc_stack[-1][0]:
					inc_stack.pop(-1)
				inc_stack.append((nums[r], r))
				min_v = inc_stack[0][0]
			while max_v - min_v > limit:
				if dec_stack[0][1] == l:
					dec_stack.pop(0)
					max_v = dec_stack[0][0]
				if inc_stack[0][1] == l:
					inc_stack.pop(0)
					min_v = inc_stack[0][0]
				l += 1
		return max_interval


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		from sortedcontainers import SortedList
		sl = SortedList()
		l = r = 0
		result = 1
		for r in range(len(nums)):
			sl.add(nums[r])
			while sl[-1] - sl[0] > limit:
				sl.remove(nums[l])
				l += 1
			result = max(len(sl), result)
		return result


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		curr_max = nums[0]
		curr_min = nums[0]
		sub_nums = []
		for num in nums:
			if abs(num - curr_max) <= limit and abs(num - curr_min) <= limit and (abs(curr_max - curr_min) <= limit):
				curr_max = max(num, curr_max)
				curr_min = min(num, curr_min)
				sub_nums.append(num)
			else:
				sub_nums.append(num)
				sub_nums.pop(0)
				curr_max = max(sub_nums)
				curr_min = min(sub_nums)
		return len(sub_nums)


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		low = None
		curr_max = None
		curr_low = -1
		max_len = 0
		min_queue = []
		max_queue = []
		for i in range(len(nums)):
			curr_num = nums[i]
			self.queue_add_max(max_queue, curr_num, i)
			self.queue_add_min(min_queue, curr_num, i)
			curr_max = max_queue[0][0]
			curr_min = min_queue[0][0]
			if curr_max - curr_min > limit:
				while curr_max - curr_min > limit and curr_low < i:
					curr_low += 1
					if curr_low == min_queue[0][1]:
						min_queue.pop(0)
					if curr_low == max_queue[0][1]:
						max_queue.pop(0)
					curr_max = max_queue[0][0]
					curr_min = min_queue[0][0]
			curr_dist = i - curr_low
			if curr_dist > max_len:
				max_len = curr_dist
		return max_len

	def queue_add_max(self, queue, element, index):
		while queue != []:
			if element > queue[len(queue) - 1][0]:
				queue.pop()
			else:
				break
		queue.append((element, index))

	def queue_add_min(self, queue, element, index):
		while queue != []:
			if element < queue[len(queue) - 1][0]:
				queue.pop()
			else:
				break
		queue.append((element, index))


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		cur_max = nums[0]
		cur_min = nums[0]
		sub_nums = []
		for i in nums:
			cur_max = max(i, cur_max)
			cur_min = min(i, cur_min)
			if cur_max - cur_min <= limit:
				sub_nums.append(i)
			else:
				sub_nums.append(i)
				sub_nums.pop(0)
				cur_max = max(sub_nums)
				cur_min = min(sub_nums)
		return len(sub_nums)


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxd = collections.deque()
		mind = collections.deque()
		i = 0
		N = len(nums)
		Lm = 0
		for j in range(N):
			a = nums[j]
			while maxd and maxd[-1] < a:
				maxd.pop()
			maxd.append(a)
			while mind and mind[-1] > a:
				mind.pop()
			mind.append(a)
			while maxd[0] - mind[0] > limit:
				if maxd[0] == nums[i]:
					maxd.popleft()
				if mind[0] == nums[i]:
					mind.popleft()
				i += 1
			Lm = max(Lm, j - i + 1)
		return Lm


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		import sortedcontainers
		sl = sortedcontainers.SortedList()
		(start, end) = (0, 0)
		best = 0
		while end < len(nums):
			sl.add(nums[end])
			if sl[-1] - sl[0] <= limit:
				best = max(best, len(sl))
			else:
				while sl[-1] - sl[0] > limit:
					sl.remove(nums[start])
					start += 1
			end += 1
		return best


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxD = []
		minD = []
		ind = 0
		res = 0
		slow = 0
		fast = 0
		while slow <= fast and fast < len(nums):
			while len(maxD) > 0 and maxD[len(maxD) - 1] < nums[fast]:
				maxD.pop(len(maxD) - 1)
			maxD.append(nums[fast])
			while len(minD) > 0 and minD[len(minD) - 1] > nums[fast]:
				minD.pop(len(minD) - 1)
			minD.append(nums[fast])
			while maxD[0] - minD[0] > limit and slow < fast:
				if maxD[0] == nums[slow]:
					maxD.pop(0)
				if minD[0] == nums[slow]:
					minD.pop(0)
				slow += 1
			res = max(res, fast - slow + 1)
			fast += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if nums is None or len(nums) == 0:
			return 0
		queue = collections.deque([])
		max_len = 0
		right = 0
		min_heap = []
		max_heap = []
		for left in range(len(nums)):
			if left == right:
				heapq.heappush(min_heap, (nums[left], left))
				heapq.heappush(max_heap, (-nums[left], left))
				right += 1
			while right < len(nums):
				cur_min = min_heap[0][0]
				cur_max = -max_heap[0][0]
				if abs(nums[right] - cur_min) > limit:
					break
				if abs(nums[right] - cur_max) > limit:
					break
				heapq.heappush(min_heap, (nums[right], right))
				heapq.heappush(max_heap, (-nums[right], right))
				right += 1
			max_len = max(max_len, right - left)
			if right == len(nums):
				return max_len
			while max_heap and max_heap[0][1] <= left:
				heapq.heappop(max_heap)
			while min_heap and min_heap[0][1] <= left:
				heapq.heappop(min_heap)
		return max_len


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		arr = nums
		lim = limit
		p1 = 0
		p2 = 0
		ans = 1
		bt = SortedList([arr[0]])
		n = len(arr)
		while p1 < n - 1 or p2 < n - 1:
			mx = bt[-1]
			mn = bt[0]
			diff = abs(mx - mn)
			if diff <= lim and ans < p2 - p1 + 1:
				ans = p2 - p1 + 1
			if p2 == n - 1 or diff > lim:
				bt.remove(arr[p1])
				p1 += 1
			else:
				p2 += 1
				bt.add(arr[p2])
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_stack = []
		min_stack = []
		left = 0
		ans = 0
		for right in range(len(nums)):
			while max_stack and nums[max_stack[-1]] < nums[right]:
				max_stack.pop()
			max_stack.append(right)
			while min_stack and nums[min_stack[-1]] > nums[right]:
				min_stack.pop()
			min_stack.append(right)
			while max_stack and min_stack and (nums[max_stack[0]] - nums[min_stack[0]] > limit):
				if max_stack[0] <= left:
					max_stack.pop(0)
				if min_stack[0] <= left:
					min_stack.pop(0)
				left += 1
			ans = max(ans, right - left + 1)
		return ans


from heapq import heappush, heappop

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_q = []
		max_q = []
		start_index = 0
		cur_longest_len = 0
		for (i, number) in enumerate(nums):
			heappush(min_q, (number, i))
			heappush(max_q, (-number, i))
			while self.calc_diff(-max_q[0][0], min_q[0][0]) > limit:
				if min_q[0][1] > max_q[0][1]:
					(value, _index) = heappop(max_q)
					q = max_q
				else:
					(value, _index) = heappop(min_q)
					q = min_q
				start_index = max(_index + 1, start_index)
				while q and q[0][1] < start_index:
					heappop(q)
			cur_longest_len = max(cur_longest_len, i - start_index + 1)
		return cur_longest_len

	def calc_diff(self, a, b):
		return abs(a - b)


import bisect

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) <= 1:
			return len(nums)
		h = [nums[0]]
		(right, left, max_len) = (0, 0, 1)
		(lo, hi) = (nums[0], nums[0])
		while right < len(nums) and left < len(nums):
			if abs(hi - lo) <= limit:
				max_len = max(max_len, right - left + 1)
				right += 1
				if right < len(nums):
					hi = max(nums[right], hi)
					lo = min(nums[right], lo)
					bisect.insort(h, nums[right])
			else:
				del h[bisect.bisect_left(h, nums[left])]
				(lo, hi) = (h[0], h[-1])
				left += 1
		return max_len


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		left = 0
		right = 0
		max_d = 0
		min_heap = [nums[0]]
		max_heap = [-nums[0]]
		local_max = nums[0]
		local_min = nums[0]
		while left < n and right < n:
			if nums[right] > local_max:
				local_max = nums[right]
			if nums[right] < local_min:
				local_min = nums[right]
			lower = local_max - limit
			upper = local_min + limit
			if lower <= nums[right] <= upper:
				if right - left + 1 > max_d:
					max_d = right - left + 1
				right += 1
				if right < n:
					heapq.heappush(min_heap, nums[right])
					heapq.heappush(max_heap, -nums[right])
			else:
				if nums[left] == min_heap[0]:
					heapq.heappop(min_heap)
				else:
					min_heap.remove(nums[left])
				if max_heap[0] == -nums[left]:
					heapq.heappop(max_heap)
				else:
					max_heap.remove(-nums[left])
				left += 1
				local_min = min_heap[0]
				local_max = -max_heap[0]
		return max_d


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:

		def addToDeqs(min_deq, max_deq, curr, start_i):
			while min_deq and min_deq[-1] > curr:
				min_deq.pop()
			min_deq.append(curr)
			while max_deq and max_deq[-1] < curr:
				max_deq.pop()
			max_deq.append(curr)
			while abs(max_deq[0] - min_deq[0]) > limit:
				if max_deq[0] == nums[start_i]:
					max_deq.pop(0)
				if min_deq[0] == nums[start_i]:
					min_deq.pop(0)
				start_i += 1
			return start_i
		min_deq = []
		max_deq = []
		longest_subarray = 0
		start_i = 0
		for (i, n) in enumerate(nums):
			start_i = addToDeqs(min_deq, max_deq, n, start_i)
			length_subarray = i - start_i + 1
			longest_subarray = max(longest_subarray, length_subarray)
		return longest_subarray


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		ans = 0
		heap1 = []
		heap2 = []
		end = 0
		start = 0
		n = len(nums)
		while end < n:
			heapq.heappush(heap1, [-nums[end], end])
			heapq.heappush(heap2, [nums[end], end])
			while -heap1[0][0] - heap2[0][0] > limit:
				start += 1
				while heap1 and heap1[0][1] < start:
					heapq.heappop(heap1)
				while heap2 and heap2[0][1] < start:
					heapq.heappop(heap2)
			ans = max(ans, end - start + 1)
			end += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		res = 0
		(left, right) = (0, 0)
		(minimum, maximum) = ([], [])
		while right < n:
			heapq.heappush(minimum, (nums[right], right))
			heapq.heappush(maximum, (-nums[right], right))
			right += 1
			while -maximum[0][0] - minimum[0][0] > limit:
				while minimum and minimum[0][1] <= left:
					heapq.heappop(minimum)
				while maximum and maximum[0][1] <= left:
					heapq.heappop(maximum)
				left += 1
			res = max(res, right - left)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_len = 1
		maxi = nums[0]
		mini = nums[0]
		start = 0
		temp = nums[start:start + 1]
		for i in range(1, len(nums)):
			temp.append(nums[i])
			if nums[i] > maxi:
				maxi = nums[i]
			if nums[i] < mini:
				mini = nums[i]
			if maxi - mini <= limit:
				max_len = max(max_len, len(temp))
			else:
				temp.pop(start)
				maxi = max(temp)
				mini = min(temp)
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxd = collections.deque()
		mind = collections.deque()
		(s, e) = (0, 0)
		res = 0
		while e < len(nums):
			while len(maxd) and nums[e] >= nums[maxd[-1]]:
				maxd.pop()
			while len(mind) and nums[e] <= nums[mind[-1]]:
				mind.pop()
			maxd.append(e)
			mind.append(e)
			if nums[maxd[0]] - nums[mind[0]] > limit:
				s += 1
				if s > mind[0]:
					mind.popleft()
				if s > maxd[0]:
					maxd.popleft()
			else:
				res = max(res, e - s + 1)
				e += 1
		return res


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		lhs = 0
		rhs = 1
		diff_len = 1
		sd = SortedList([nums[lhs]])
		while rhs < len(nums):
			sd.add(nums[rhs])
			if sd[len(sd) - 1] - sd[0] <= limit:
				diff_len = max(diff_len, rhs - lhs + 1)
			else:
				sd.discard(nums[lhs])
				lhs += 1
			rhs += 1
		return diff_len


class MinMaxList(object):

	def __init__(self):
		self._container = {}
		self._max = -6665677
		self._min = 6665677

	def min_val(self) -> int:
		return self._min

	def max_val(self) -> int:
		return self._max

	def append_val(self, val: int):
		if val in self._container:
			self._container[val] = self._container[val] + 1
		else:
			self._container[val] = 1
		self._max = max(val, self._max)
		self._min = min(val, self._min)

	def remove_val(self, val: int):
		if val in self._container:
			if self._container[val] > 1:
				self._container[val] = self._container[val] - 1
				return
			else:
				del self._container[val]
		if self._max == val:
			self._max = max(self._container.keys())
		if self._min == val:
			self._min = min(self._container.keys())

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		diff = 0
		max_result = 0
		max_subarray = 0
		low = 0
		high = 0
		window = MinMaxList()
		while high < len(nums):
			window.append_val(nums[high])
			high = high + 1
			max_subarray = max_subarray + 1
			diff = abs(window.max_val() - window.min_val())
			while diff > limit:
				window.remove_val(nums[low])
				low = low + 1
				max_subarray = max_subarray - 1
				diff = abs(window.max_val() - window.min_val())
			max_result = max(max_subarray, max_result)
		return max_result


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		l = len(nums)
		if l == 1:
			if limit >= 0:
				return 1
			return 0
		max_count = i = 0
		j = 1

		def get_min():
			while min_list[0][1] < i:
				heappop(min_list)
			return min_list[0][1]

		def get_max():
			while max_list[0][1] < i:
				heappop(max_list)
			return max_list[0][1]
		min_list = []
		max_list = []
		heappush(min_list, (nums[0], 0))
		heappush(max_list, (-nums[0], 0))
		while l > j >= i:
			heappush(min_list, (nums[j], j))
			heappush(max_list, (-nums[j], j))
			mn = get_min()
			mx = get_max()
			diff = nums[mx] - nums[mn]
			if diff > limit:
				if j != i + 1:
					max_count = max(max_count, j - i)
					i = min(mn, mx) + 1
				else:
					j += 1
					i += 1
			else:
				j += 1
		if j == l and i < j - 1:
			max_count = max(max_count, j - i)
		return max_count


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		curr_max = deque([])
		curr_min = deque([])
		i = 0
		j = 0
		res = 0
		while i <= j and j < len(nums):
			num = nums[j]
			while curr_max and curr_max[-1] < num:
				curr_max.pop()
			else:
				curr_max.append(num)
			while curr_min and curr_min[-1] > num:
				curr_min.pop()
			else:
				curr_min.append(num)
			if curr_max[0] - curr_min[0] <= limit:
				res = max(res, j - i + 1)
			else:
				value = nums[i]
				if value == curr_max[0]:
					curr_max.popleft()
				if value == curr_min[0]:
					curr_min.popleft()
				i += 1
			j += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		min_deque = [nums[0]]
		max_deque = [nums[0]]
		max_stretch = 1
		start = 0
		end = 0
		while end < len(nums) - 1:
			end += 1
			while len(min_deque) > 0 and nums[end] < min_deque[-1]:
				min_deque.pop()
			min_deque.append(nums[end])
			while len(max_deque) > 0 and nums[end] > max_deque[-1]:
				max_deque.pop()
			max_deque.append(nums[end])
			while max_deque[0] - min_deque[0] > limit:
				if min_deque[0] == nums[start]:
					min_deque.pop(0)
				if max_deque[0] == nums[start]:
					max_deque.pop(0)
				start += 1
			if end - start + 1 > max_stretch:
				max_stretch = end - start + 1
		return max_stretch


from sortedcontainers import SortedDict

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		startWindow = 0
		runningDict = SortedDict()
		maxWindow = 0
		for endWindow in range(len(nums)):
			if nums[endWindow] not in runningDict:
				runningDict[nums[endWindow]] = 0
			runningDict[nums[endWindow]] += 1
			(minKey, maxKey) = (runningDict.peekitem(0), runningDict.peekitem(-1))
			(minKey, maxKey) = (minKey[0], maxKey[0])
			while abs(maxKey - minKey) > limit and startWindow < endWindow:
				runningDict[nums[startWindow]] -= 1
				if runningDict[nums[startWindow]] == 0:
					del runningDict[nums[startWindow]]
				(minKey, maxKey) = (runningDict.peekitem(0), runningDict.peekitem(-1))
				(minKey, maxKey) = (minKey[0], maxKey[0])
				startWindow += 1
			maxWindow = max(maxWindow, endWindow - startWindow + 1)
		return maxWindow


import heapq

class Item:
	(val, index) = (0, 0)

	def __lt__(self, other):
		return self.val < other.val

	def __init__(self, val, index):
		self.val = val
		self.index = index

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxheap, minheap) = ([], [])
		index = 0
		maxLen = 0
		leftIndex = -1
		while index < len(nums):
			while len(minheap) > 0 and (minheap[0].val < nums[index] - limit or minheap[0].index < leftIndex):
				leftIndex = max(leftIndex, heapq.heappop(minheap).index)
			while len(maxheap) > 0 and (-maxheap[0].val > nums[index] + limit or maxheap[0].index < leftIndex):
				leftIndex = max(leftIndex, heapq.heappop(maxheap).index)
			heapq.heappush(minheap, Item(nums[index], index))
			heapq.heappush(maxheap, Item(-nums[index], index))
			maxLen = max(maxLen, index - leftIndex)
			index += 1
		return maxLen


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		l = ans = 0
		(maxh, minh) = ([], [])
		for (r, num) in enumerate(nums):
			heapq.heappush(maxh, (-1 * num, r))
			heapq.heappush(minh, (num, r))
			while maxh[0][0] * -1 - minh[0][0] > limit:
				while maxh[0][1] <= l:
					heapq.heappop(maxh)
				while minh[0][1] <= l:
					heapq.heappop(minh)
				l += 1
			ans = max(ans, r - l + 1)
		return ans


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(maxq, minq) = ([], [])
		res = i = 0
		for (j, a) in enumerate(nums):
			heapq.heappush(maxq, [-a, j])
			heapq.heappush(minq, [a, j])
			while -maxq[0][0] - minq[0][0] > limit:
				i = min(maxq[0][1], minq[0][1]) + 1
				while maxq[0][1] < i:
					heapq.heappop(maxq)
				while minq[0][1] < i:
					heapq.heappop(minq)
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxque = collections.deque([])
		minque = collections.deque([])
		start = end = 0
		count = 0
		while end < len(nums):
			while len(maxque) and nums[end] > nums[maxque[-1]]:
				maxque.pop()
			while len(minque) and nums[end] < nums[minque[-1]]:
				minque.pop()
			maxque.append(end)
			minque.append(end)
			if nums[maxque[0]] - nums[minque[0]] > limit:
				if maxque[0] == start:
					maxque.popleft()
				if minque[0] == start:
					minque.popleft()
				start += 1
				end += 1
			else:
				end += 1
		return len(nums) - start


import collections

class minQueue(object):

	def __init__(self):
		self.queue = collections.deque()

	def append(self, val, idx):
		while self.queue and self.queue[-1][0] > val:
			self.queue.pop()
		self.queue.append((val, idx))

	def getMin(self, left_idx):
		while self.queue and self.queue[0][1] < left_idx:
			self.queue.popleft()
		return self.queue[0][0]

class maxQueue(object):

	def __init__(self):
		self.queue = collections.deque()

	def append(self, val, idx):
		while self.queue and self.queue[-1][0] < val:
			self.queue.pop()
		self.queue.append((val, idx))

	def getMax(self, left_idx):
		while self.queue and self.queue[0][1] < left_idx:
			self.queue.popleft()
		return self.queue[0][0]

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minQ = minQueue()
		maxQ = maxQueue()
		(l, r) = (0, 0)
		minQ.append(nums[0], 0)
		maxQ.append(nums[0], 0)
		cond = True
		n = len(nums)
		res = 0
		while l <= r and r < n:
			while r < n and cond:
				res = max(res, r - l + 1)
				r += 1
				if r < n:
					maxQ.append(nums[r], r)
					minQ.append(nums[r], r)
					cond = maxQ.getMax(l) - minQ.getMin(l) <= limit
			while l <= r and (not cond):
				l += 1
				cond = maxQ.getMax(l) - minQ.getMin(l) <= limit
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		if len(nums) == 1:
			return 1
		l = 0
		r = 1
		curmax = nums[0]
		curmin = nums[0]
		maxlen = 1
		while l <= r and r < len(nums):
			curmax = max(curmax, nums[r])
			curmin = min(curmin, nums[r])
			if curmax - curmin <= limit:
				maxlen = max(maxlen, r - l + 1)
			else:
				if nums[l] == curmax:
					curmax = max(nums[l + 1:r + 1])
				if nums[l] == curmin:
					curmin = min(nums[l + 1:r + 1])
				l += 1
			r += 1
		return maxlen


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		l = 0
		thing = 0
		curMin = 9999999
		curMax = -9999999
		numMap = {}
		i = 0
		while i < len(nums):
			if nums[i] not in numMap:
				numMap[nums[i]] = 0
			numMap[nums[i]] += 1
			curMax = max(curMax, nums[i])
			curMin = min(curMin, nums[i])
			i += 1
			if curMax - curMin <= limit:
				thing = max(thing, i - l)
			else:
				p = nums[l]
				numMap[nums[l]] -= 1
				if numMap[nums[l]] == 0:
					del numMap[nums[l]]
				l = l + 1
				if p == curMin or p == curMax:
					curMin = min(numMap)
					curMax = max(numMap)
		return thing


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		count = collections.defaultdict(int)
		min_heap = []
		max_heap = []
		ans = []
		max_length = 0
		for num in nums:
			ans.append(num)
			count[num] += 1
			if count[num] == 1:
				heapq.heappush(min_heap, num)
				heapq.heappush(max_heap, num * -1)
			max_val = abs(max_heap[0])
			min_val = min_heap[0]
			while max_val - min_val > limit:
				popped_val = ans.pop(0)
				count[popped_val] -= 1
				if popped_val == min_val and count[popped_val] == 0:
					while count[min_val] == 0:
						heapq.heappop(min_heap)
						min_val = min_heap[0]
				if popped_val == max_val and count[popped_val] == 0:
					while count[max_val] == 0:
						heapq.heappop(max_heap)
						max_val = abs(max_heap[0])
			max_length = max(max_length, len(ans))
		return max_length


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		start = 0
		result = 0
		minHeap = []
		maxHeap = []
		for i in range(len(nums)):
			heapq.heappush(minHeap, [nums[i], i])
			heapq.heappush(maxHeap, [-nums[i], i])
			while -maxHeap[0][0] - minHeap[0][0] > limit:
				start = min(maxHeap[0][1], minHeap[0][1]) + 1
				while minHeap and minHeap[0][1] < start:
					heapq.heappop(minHeap)
				while maxHeap and maxHeap[0][1] < start:
					heapq.heappop(maxHeap)
			result = max(result, i - start + 1)
		return result


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 0:
			return 0
		max_q = MonoQueue(False)
		min_q = MonoQueue(True)
		(l, r) = (0, 0)
		max_q.push(nums[0])
		min_q.push(nums[0])

		def in_limit():
			if max_q.is_empty() is True:
				return True
			return abs(max_q.top() - min_q.top()) <= limit
		res = 0
		while r < len(nums):
			if in_limit() is True:
				res = max(res, r - l + 1)
				r += 1
				if r < len(nums):
					min_q.push(nums[r])
					max_q.push(nums[r])
			else:
				min_q.popfront(nums[l])
				max_q.popfront(nums[l])
				l += 1
		return res

class MonoQueue:

	def __init__(self, inc=True):
		self.queue = []
		self.inc = inc

	def popfront(self, n):
		if self.queue[0] == n:
			self.queue.pop(0)
		return

	def push(self, n):
		while self.queue:
			if self.inc is True and self.queue[-1] > n:
				self.queue.pop(-1)
			elif self.inc is False and self.queue[-1] < n:
				self.queue.pop(-1)
			else:
				break
		self.queue.append(n)
		return

	def is_empty(self):
		return len(self.queue) == 0

	def top(self):
		return self.queue[0]


import heapq

class Solution:

	def __init__(self):
		self.nums = None
		self.start = None
		self.end = None
		self.q = []
		self.qmx = []

	def initialize(self):
		self.start = 0
		self.end = 0
		heapq.heappush(self.q, [self.nums[0], 0])
		heapq.heappush(self.qmx, [self.nums[0] * -1, 0])

	def moveStartRight(self):
		count = 0
		minValuePos = self.q[0][1]
		maxValuePos = self.qmx[0][1]
		self.start = min(minValuePos, maxValuePos) + 1
		while self.q[0][1] < self.start:
			heapq.heappop(self.q)
		while self.qmx[0][1] < self.start:
			heapq.heappop(self.qmx)

	def moveEndRight(self):
		self.end += 1
		if self.end < len(self.nums):
			heapq.heappush(self.q, [self.nums[self.end], self.end])
			heapq.heappush(self.qmx, [self.nums[self.end] * -1, self.end])

	def getMinMax(self):
		return (self.q[0][0], self.qmx[0][0] * -1)

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		self.nums = nums
		self.initialize()
		size = 0
		while self.end < len(self.nums):
			(minValue, maxValue) = self.getMinMax()
			if maxValue - minValue <= limit:
				size = max(size, self.end - self.start + 1)
				self.moveEndRight()
			else:
				self.moveStartRight()
		return size


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minheap = []
		maxheap = []
		heapq.heapify(minheap)
		heapq.heapify(maxheap)
		heapq.heappush(minheap, [nums[0], 0])
		heapq.heappush(maxheap, [-nums[0], 0])
		begin = 0
		length = 1
		end = 1
		next_idx = 0
		while begin <= end and end <= len(nums) - 1:
			if abs(minheap[0][0] - nums[end]) <= limit and abs(abs(maxheap[0][0]) - nums[end]) <= limit:
				length = max(length, end - begin + 1)
			else:
				while len(minheap) > 0 and abs(minheap[0][0] - nums[end]) > limit:
					(ele, idx) = heapq.heappop(minheap)
					next_idx = max(next_idx, idx)
				while len(maxheap) > 0 and abs(-maxheap[0][0] - nums[end]) > limit:
					(ele, idx) = heapq.heappop(maxheap)
					next_idx = max(next_idx, idx)
				begin = next_idx + 1
			heapq.heappush(minheap, [nums[end], end])
			heapq.heappush(maxheap, [-nums[end], end])
			end += 1
		return length


class MinMaxStack:

	def __init__(self):
		self.s = []
		self.mins = []
		self.maxes = []

	def append(self, x):
		self.s.append(x)
		if not self.mins or x <= self.mins[-1]:
			self.mins.append(x)
		if not self.maxes or x >= self.maxes[-1]:
			self.maxes.append(x)

	def pop(self):
		x = self.s.pop()
		if x == self.mins[-1]:
			self.mins.pop()
		if x == self.maxes[-1]:
			self.maxes.pop()
		return x

	def min(self):
		return self.mins[-1] if self.mins else float('inf')

	def max(self):
		return self.maxes[-1] if self.maxes else -float('inf')

	def __len__(self):
		return len(self.s)

class MinMaxQueue:

	def __init__(self):
		self.s1 = MinMaxStack()
		self.s2 = MinMaxStack()

	def enqueue(self, x):
		self.s1.append(x)

	def dequeue(self):
		if not self.s2:
			while self.s1:
				to_append = self.s1.pop()
				self.s2.append(to_append)
		return self.s2.pop()

	def min(self):
		return min(self.s1.min(), self.s2.min())

	def max(self):
		return max(self.s1.max(), self.s2.max())

	def __len__(self):
		return len(self.s1) + len(self.s2)

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		i = 0
		max_len = 1
		q = MinMaxQueue()
		q.enqueue(nums[0])
		while i < len(nums):
			if q.max() - q.min() <= limit:
				max_len = max(max_len, len(q))
				i += 1
				if i < len(nums):
					q.enqueue(nums[i])
				continue
			q.dequeue()
		return max_len


from sortedcontainers import SortedList

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		start = 0
		n = len(nums)
		k = limit
		s = SortedList()
		max_count = 0
		for i in range(n):
			s.add(nums[i])
			if s[-1] - s[0] > k:
				while s[-1] - s[0] > k:
					s.remove(nums[start])
					start += 1
			max_count = max(max_count, len(s))
		return max_count


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 1:
			return 1
		left = right = 0
		min_n = max_n = nums[0]
		max_size = 0
		while right < len(nums):
			if nums[right] > max_n:
				max_n = nums[right]
			if nums[right] < min_n:
				min_n = nums[right]
			while max_n - min_n > limit:
				left += 1
				min_n = min(nums[left:right + 1])
				max_n = max(nums[left:right + 1])
				break
			if right - left > max_size:
				max_size = right - left
			right += 1
		return max_size + 1


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minq = deque()
		maxq = deque()
		ret = l = 0
		for i in range(len(nums)):
			while minq and nums[i] < minq[-1]:
				minq.pop()
			minq.append(nums[i])
			while maxq and nums[i] > maxq[-1]:
				maxq.pop()
			maxq.append(nums[i])
			while maxq[0] - minq[0] > limit:
				if nums[l] == maxq[0]:
					maxq.popleft()
				if nums[l] == minq[0]:
					minq.popleft()
				l += 1
			ret = max(ret, i - l + 1)
		return ret


from sortedcontainers import SortedDict

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		window_multiset = SortedDict()
		start = 0
		end = start
		ret = 0
		while start < len(nums) and end < len(nums):
			if self.can_add(window_multiset, nums[end], limit):
				window_multiset[nums[end]] = window_multiset.get(nums[end], 0) + 1
				end += 1
			else:
				ret = max(end - start, ret)
				window_multiset[nums[end]] = window_multiset.get(nums[end], 0) + 1
				while not self.is_valid_window(window_multiset, limit):
					self.remove_multiset(window_multiset, nums[start])
					start += 1
				end += 1
		ret = max(end - start, ret)
		return ret

	def remove_multiset(self, window_multiset: SortedDict, num: int):
		window_multiset[num] -= 1
		if not window_multiset[num]:
			window_multiset.pop(num)

	def is_valid_window(self, window_multiset: SortedDict, limit: int) -> bool:
		view = window_multiset.keys()
		return view[-1] - view[0] <= limit

	def can_add(self, window_multiset: SortedDict, cand: int, limit: int) -> bool:
		if not len(window_multiset):
			return True
		view = window_multiset.keys()
		return abs(cand - view[0]) <= limit and abs(cand - view[-1]) <= limit


import sortedcontainers

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		window = sortedcontainers.SortedList()
		N = len(nums)
		left = 0
		right = -1

		def check():
			if not window:
				return True
			return window[-1] - window[0] <= limit
		ret = 1
		while left < N and right < N:
			if not check():
				window.remove(nums[left])
				left += 1
			else:
				ret = max(ret, right - left + 1)
				right += 1
				if right < N:
					window.add(nums[right])
		return ret


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		i = 0
		j = 0
		max_length = 1
		cur_max = cur_min = nums[0]
		while j < len(nums):
			dif = cur_max - cur_min
			if dif <= limit:
				max_length = j - i + 1
				j += 1
				if j < len(nums):
					cur_max = max(cur_max, nums[j])
					cur_min = min(cur_min, nums[j])
			else:
				i += 1
				j += 1
				cur_max = max(nums[i:j + 1])
				cur_min = min(nums[i:j + 1])
		return max_length


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		result = 1
		start = 0
		end = start + result
		mini = float('inf')
		maxi = float('-inf')
		while end <= len(nums):
			mini = min(nums[start:end])
			maxi = max(nums[start:end])
			if abs(mini - maxi) > limit:
				start += 1
				end += 1
			else:
				end += 1
				while end <= len(nums):
					mini = min(nums[end - 1], mini)
					maxi = max(nums[end - 1], maxi)
					if abs(mini - maxi) > limit:
						result = max(result, end - start - 1)
						start += 1
						end = start + result
						break
					else:
						end += 1
						if end > len(nums):
							result = max(result, end - start - 1)
		return result


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		N = len(nums)
		ans = 0
		maxi = deque()
		mini = deque()
		j = 0
		for i in range(N):
			while mini and nums[i] < nums[mini[-1]]:
				mini.pop()
			while maxi and nums[i] > nums[maxi[-1]]:
				maxi.pop()
			mini.append(i)
			maxi.append(i)
			if abs(nums[maxi[0]] - nums[mini[0]]) <= limit:
				ans = max(ans, abs(maxi[0] - mini[0]) + 1)
			else:
				while mini and mini[0] <= j:
					mini.popleft()
				while maxi and maxi[0] <= j:
					maxi.popleft()
				j += 1
		return N - j


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		minQ = deque()
		maxQ = deque()
		ans = -1
		l = 0
		for r in range(len(nums)):
			while minQ and nums[r] < minQ[-1]:
				minQ.pop()
			while maxQ and nums[r] > maxQ[-1]:
				maxQ.pop()
			minQ.append(nums[r])
			maxQ.append(nums[r])
			while abs(maxQ[0] - minQ[0]) > limit:
				if minQ and minQ[0] == nums[l]:
					minQ.popleft()
				if maxQ and maxQ[0] == nums[l]:
					maxQ.popleft()
				l += 1
			ans = max(ans, r - l + 1)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		l = 0
		min_dq = deque()
		max_dq = deque()
		out = 0
		for r in range(len(nums)):
			val = nums[r]
			while min_dq and val < nums[min_dq[-1]]:
				min_dq.pop()
			while max_dq and val > nums[max_dq[-1]]:
				max_dq.pop()
			max_dq.append(r)
			min_dq.append(r)
			while nums[max_dq[0]] - nums[min_dq[0]] > limit:
				l += 1
				if max_dq[0] < l:
					max_dq.popleft()
				if min_dq[0] < l:
					min_dq.popleft()
			out = max(out, r - l + 1)
		return out


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		decStack = collections.deque()
		incStack = collections.deque()
		ans = 0
		l = 0
		for (r, n) in enumerate(nums):
			while decStack and decStack[-1][0] <= n:
				decStack.pop()
			decStack.append((n, r))
			while incStack and incStack[-1][0] >= n:
				incStack.pop()
			incStack.append((n, r))
			while decStack[0][0] - incStack[0][0] > limit:
				l = min(incStack[0][1], decStack[0][1]) + 1
				while decStack and decStack[0][1] < l:
					decStack.popleft()
				while incStack and incStack[0][1] < l:
					incStack.popleft()
			ans = max(ans, r - l + 1)
		return ans


import collections

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(mx, mn) = (collections.deque([0]), collections.deque([0]))
		ans = 1
		left = 0
		for i in range(1, len(nums)):
			while mx and nums[mx[-1]] < nums[i]:
				mx.pop()
			mx.append(i)
			while mn and nums[mn[-1]] > nums[i]:
				mn.pop()
			mn.append(i)
			while mx and mn and (nums[mx[0]] - nums[mn[0]] > limit):
				left += 1
				if mx[0] < left:
					mx.popleft()
				if mn[0] < left:
					mn.popleft()
			ans = max(ans, i - left + 1)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxq = collections.deque()
		minq = collections.deque()
		start = 0
		for (i, n) in enumerate(nums):
			while maxq and maxq[-1][0] < n:
				maxq.pop()
			while minq and minq[-1][0] > n:
				minq.pop()
			maxq.append([n, i])
			minq.append([n, i])
			if maxq[0][0] - minq[0][0] > limit:
				if maxq[0][0] == nums[start]:
					maxq.popleft()
				if minq[0][0] == nums[start]:
					minq.popleft()
				start += 1
		return len(nums) - start


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_elements = collections.deque()
		min_elements = collections.deque()
		max_len = 0
		i = 0
		for (j, num) in enumerate(nums):
			while max_elements and max_elements[-1] < num:
				max_elements.pop()
			while min_elements and min_elements[-1] > num:
				min_elements.pop()
			max_elements.append(num)
			min_elements.append(num)
			while max_elements[0] - min_elements[0] > limit:
				if max_elements and max_elements[0] == nums[i]:
					max_elements.popleft()
				if min_elements and min_elements[0] == nums[i]:
					min_elements.popleft()
				i += 1
			max_len = max(max_len, j - i + 1)
		return max_len


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		mindeque = deque()
		maxdeque = deque()
		L = R = 0
		res = 0
		while R < len(nums):
			while mindeque and nums[mindeque[-1]] > nums[R]:
				mindeque.pop()
			mindeque.append(R)
			while maxdeque and nums[maxdeque[-1]] < nums[R]:
				maxdeque.pop()
			maxdeque.append(R)
			if nums[maxdeque[0]] - nums[mindeque[0]] <= limit:
				res = max(res, R - L + 1)
			else:
				while nums[maxdeque[0]] - nums[mindeque[0]] > limit:
					if L == maxdeque[0]:
						maxdeque.popleft()
					if L == mindeque[0]:
						mindeque.popleft()
					L += 1
			R += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		from collections import deque
		(asc, desc) = (deque(), deque())
		(l, r) = (0, 0)
		res = 0
		while r < len(nums):
			while asc and nums[asc[-1]] >= nums[r]:
				asc.pop()
			while desc and nums[desc[-1]] <= nums[r]:
				desc.pop()
			asc.append(r)
			desc.append(r)
			while nums[desc[0]] - nums[asc[0]] > limit:
				l += 1
				if desc[0] < l:
					desc.popleft()
				if asc[0] < l:
					asc.popleft()
			res = max(res, r - l + 1)
			r += 1
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		mindeq = deque()
		maxdeq = deque()
		i = 0
		ans = 1
		for j in range(0, len(nums)):
			while len(maxdeq) > 0 and maxdeq[-1] < nums[j]:
				maxdeq.pop()
			maxdeq.append(nums[j])
			while len(mindeq) > 0 and mindeq[-1] > nums[j]:
				mindeq.pop()
			mindeq.append(nums[j])
			if maxdeq[0] - mindeq[0] > limit:
				if maxdeq[0] == nums[i]:
					maxdeq.popleft()
				if mindeq[0] == nums[i]:
					mindeq.popleft()
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_list = []
		min_list = []
		j = 0
		for i in range(len(nums)):
			while max_list and max_list[-1] < nums[i]:
				max_list.pop()
			while min_list and min_list[-1] > nums[i]:
				min_list.pop()
			max_list.append(nums[i])
			min_list.append(nums[i])
			if max_list[0] - min_list[0] > limit:
				if max_list[0] == nums[j]:
					max_list = max_list[1:]
				if min_list[0] == nums[j]:
					min_list = min_list[1:]
				j += 1
		return len(nums) - j


class Solution:

	def longestSubarray(self, nums, limit):
		(mini, maxi, res, i) = (deque([]), deque([]), 0, 0)
		for j in range(len(nums)):
			while mini and mini[-1][0] > nums[j]:
				mini.pop()
			mini.append((nums[j], j))
			while maxi and maxi[-1][0] < nums[j]:
				maxi.pop()
			maxi.append((nums[j], j))
			while abs(maxi[0][0] - mini[0][0]) > limit and i < j:
				if maxi[0][-1] <= i:
					maxi.popleft()
				elif mini[0][-1] <= i:
					mini.popleft()
				i += 1
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_deque = collections.deque()
		min_deque = collections.deque()
		n = len(nums)
		l = 0
		res = 0
		for r in range(n):
			self.push_max_deque(max_deque, nums, r)
			self.push_min_deque(min_deque, nums, r)
			while nums[max_deque[0]] - nums[min_deque[0]] > limit:
				if max_deque[0] == l:
					max_deque.popleft()
				if min_deque[0] == l:
					min_deque.popleft()
				l += 1
			res = max(res, r - l + 1)
		return res

	def push_max_deque(self, max_deque, nums, i):
		while max_deque and nums[max_deque[-1]] < nums[i]:
			max_deque.pop()
		max_deque.append(i)

	def push_min_deque(self, min_deque, nums, i):
		while min_deque and nums[min_deque[-1]] > nums[i]:
			min_deque.pop()
		min_deque.append(i)


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		ans = 0
		start_pos = 0
		(inc, dec) = (deque([]), deque([]))
		for i in range(len(nums)):
			while len(inc) > 0 and nums[inc[-1]] > nums[i]:
				inc.pop()
			inc.append(i)
			while len(dec) > 0 and nums[dec[-1]] < nums[i]:
				dec.pop()
			dec.append(i)
			while abs(nums[inc[0]] - nums[dec[0]]) > limit:
				start_pos += 1
				if inc[0] < start_pos:
					inc.popleft()
				if dec[0] < start_pos:
					dec.popleft()
			ans = max(ans, i - start_pos + 1)
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(i, j) = (0, 0)
		nums.append(float('inf'))
		qmin = collections.deque()
		qmax = collections.deque()
		qmin.append(0)
		qmax.append(0)
		ans = 0
		while j < len(nums) - 1:
			while j < len(nums) - 1 and nums[qmax[0]] - nums[qmin[0]] <= limit:
				ans = max(ans, j - i + 1)
				j += 1
				while qmax and nums[qmax[-1]] < nums[j]:
					qmax.pop()
				qmax.append(j)
				while qmin and nums[qmin[-1]] > nums[j]:
					qmin.pop()
				qmin.append(j)
			while qmax and nums[qmax[0]] - nums[j] > limit:
				i = qmax.popleft() + 1
			while qmin and nums[j] - nums[qmin[0]] > limit:
				i = qmin.popleft() + 1
		return ans


from queue import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 1:
			return 1
		print(nums)
		decreasing = deque()
		increasing = deque()
		max_l = 1
		if abs(nums[1] - nums[0]) <= limit:
			max_l = 2
		p0 = 0
		p1 = 0
		while p1 <= len(nums) - 1:
			while decreasing and nums[decreasing[-1]] < nums[p1]:
				decreasing.pop()
			while increasing and nums[increasing[-1]] > nums[p1]:
				increasing.pop()
			while decreasing and decreasing[0] < p0:
				decreasing.popleft()
			while increasing and increasing[0] < p0:
				increasing.popleft()
			decreasing.append(p1)
			increasing.append(p1)
			while p0 < p1 and nums[decreasing[0]] - nums[increasing[0]] > limit:
				if decreasing[0] == p0:
					decreasing.popleft()
				if increasing[0] == p0:
					increasing.popleft()
				p0 += 1
			if nums[decreasing[0]] - nums[increasing[0]] <= limit:
				max_l = max(max_l, p1 - p0 + 1)
			p1 += 1
		return max_l


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if len(nums) == 1 and limit >= 0:
			return 1
		longest_subarray = 0
		right = 0
		left = 0
		min_val = nums[left]
		max_val = nums[left]
		min_dq = []
		max_dq = []
		while right < len(nums):
			while len(min_dq) > 0 and min_dq[-1] > nums[right]:
				min_dq.pop()
			min_dq.append(nums[right])
			while len(max_dq) > 0 and max_dq[-1] < nums[right]:
				max_dq.pop()
			max_dq.append(nums[right])
			min_val = min_dq[0]
			max_val = max_dq[0]
			if abs(min_val - max_val) > limit:
				if min_dq[0] == nums[left]:
					min_dq.pop(0)
				if max_dq[0] == nums[left]:
					max_dq.pop(0)
				left += 1
			longest_subarray = max(longest_subarray, right - left + 1)
			right += 1
		return longest_subarray


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		sP = 0
		eP = 0
		minQ = collections.deque([])
		maxQ = collections.deque([])
		maxSize = 0
		while eP < len(nums):
			while minQ and minQ[-1][0] > nums[eP]:
				minQ.pop()
			minQ.append((nums[eP], eP))
			while maxQ and maxQ[-1][0] < nums[eP]:
				maxQ.pop()
			maxQ.append((nums[eP], eP))
			while abs(maxQ[0][0] - minQ[0][0]) > limit and sP < eP:
				if maxQ[0][1] <= sP:
					maxQ.popleft()
				elif minQ[0][1] <= sP:
					minQ.popleft()
				sP += 1
			maxSize = max(maxSize, eP - sP + 1)
			eP += 1
		return maxSize


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		i = 0
		j = 0
		bestSize = 0
		maxVals = []
		minVals = []
		import heapq
		while j < len(nums):
			heappush(maxVals, (-nums[j], j))
			heappush(minVals, (nums[j], j))
			if -maxVals[0][0] - minVals[0][0] > limit:
				i = min(minVals[0][1], maxVals[0][1]) + 1
				while minVals[0][1] < i:
					heappop(minVals)
				while maxVals[0][1] < i:
					heappop(maxVals)
			bestSize = max(bestSize, j - i + 1)
			j += 1
		return bestSize


from collections import deque

def addMinStack(stack, val):
	while stack and stack[-1] > val:
		stack.pop()
	stack.append(val)

def addMaxStack(stack, val):
	while stack and stack[-1] < val:
		stack.pop()
	stack.append(val)

def delStack(stack, val):
	if stack and stack[0] == val:
		stack.popleft()

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		minstack = deque([])
		maxstack = deque([])
		start = 0
		end = 0
		maxSubArray = 0
		while end < len(nums):
			addMinStack(minstack, nums[end])
			addMaxStack(maxstack, nums[end])
			if maxstack[0] - minstack[0] > limit:
				while maxstack[0] - minstack[0] > limit:
					delStack(minstack, nums[start])
					delStack(maxstack, nums[start])
					start += 1
			maxSubArray = max(maxSubArray, end - start + 1)
			end += 1
		return maxSubArray


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		start = 0
		end = 0
		res = 0
		max_q = deque()
		min_q = deque()
		while end < len(nums):
			while max_q and nums[max_q[-1]] <= nums[end]:
				max_q.pop()
			while min_q and nums[min_q[-1]] >= nums[end]:
				min_q.pop()
			max_q.append(end)
			min_q.append(end)
			while nums[max_q[0]] - nums[min_q[0]] > limit:
				start += 1
				if start > max_q[0]:
					max_q.popleft()
				if start > min_q[0]:
					min_q.popleft()
			print(end - start + 1)
			res = max(res, end - start + 1)
			end += 1
		return res


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		N = len(nums)
		(max_q, min_q) = (deque([]), deque([]))
		(left, right) = (0, 0)
		max_length = 0
		while right < N:
			while max_q and max_q[-1][1] <= nums[right]:
				max_q.pop()
			max_q.append([right, nums[right]])
			while min_q and min_q[-1][1] >= nums[right]:
				min_q.pop()
			min_q.append([right, nums[right]])
			while max_q[0][1] - min_q[0][1] > limit:
				left += 1
				if max_q[0][0] < left:
					max_q.popleft()
				if min_q[0][0] < left:
					min_q.popleft()
			max_length = max(max_length, right - left + 1)
			right += 1
		return max_length


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		max_q = deque()
		min_q = deque()
		start = 0
		ans = 0
		for end in range(n):
			while max_q and max_q[-1] < nums[end]:
				max_q.pop()
			while min_q and min_q[-1] > nums[end]:
				min_q.pop()
			max_q.append(nums[end])
			min_q.append(nums[end])
			if max_q[0] - min_q[0] > limit:
				if max_q[0] == nums[start]:
					max_q.popleft()
				if min_q[0] == nums[start]:
					min_q.popleft()
				start += 1
			ans = max(end - start + 1, ans)
		return ans

	def longestSubarray2(self, nums: List[int], limit: int) -> int:
		q = deque()
		min_q = deque()
		max_q = deque()
		ans = 0
		for num in nums:
			q.append(num)
			while min_q and min_q[-1] > num:
				min_q.pop()
			min_q.append(num)
			while max_q and max_q[-1] < num:
				max_q.pop()
			max_q.append(num)
			while q and max_q[0] - min_q[0] > limit:
				del_num = q.popleft()
				if max_q[0] == del_num:
					max_q.popleft()
				if min_q[0] == del_num:
					min_q.popleft()
			ans = max(ans, len(q))
		return ans

	def longestSubarray2(self, nums: List[int], limit: int) -> int:
		min_q = deque()
		max_q = deque()
		start = 0
		for num in nums:
			while min_q and min_q[-1] > num:
				min_q.pop()
			min_q.append(num)
			while max_q and max_q[-1] < num:
				max_q.pop()
			max_q.append(num)
			if max_q[0] - min_q[0] > limit:
				if max_q[0] == nums[start]:
					max_q.popleft()
				if min_q[0] == nums[start]:
					min_q.popleft()
				start += 1
		return len(nums) - start

	def longestSubarray2(self, nums: List[int], limit: int) -> int:
		n = len(nums)
		min_dp = [[0 for _ in range(n)] for _ in range(n)]
		max_dp = [[0 for _ in range(n)] for _ in range(n)]
		ans = 1 if 0 <= limit else 0
		for i in range(n):
			min_dp[i][i] = nums[i]
			max_dp[i][i] = nums[i]
		for k in range(2, n + 1):
			for i in range(n - k + 1):
				j = i + k - 1
				min_dp[i][j] = min(min_dp[i][j - 1], nums[j])
				max_dp[i][j] = max(max_dp[i][j - 1], nums[j])
				if max_dp[i][j] - min_dp[i][j] <= limit:
					ans = k
		return ans


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(mx, mn) = (deque([0]), deque([0]))
		result = 1
		l = 0
		for i in range(1, len(nums)):
			while len(mx) != 0 and nums[mx[-1]] < nums[i]:
				mx.pop()
			mx.append(i)
			while len(mn) != 0 and nums[mn[-1]] > nums[i]:
				mn.pop()
			mn.append(i)
			while mx and mn and (nums[mx[0]] - nums[mn[0]] > limit):
				l += 1
				while mx[0] < l:
					mx.popleft()
				while mn[0] < l:
					mn.popleft()
			result = max(result, i - l + 1)
		return result


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		sd = collections.deque()
		ld = collections.deque()

		def smallpush(d, i):
			while d and d[-1][0] > nums[i]:
				d.pop()
			d.append((nums[i], i))

		def largepush(d, i):
			while d and d[-1][0] < nums[i]:
				d.pop()
			d.append((nums[i], i))

		def popleft(d, j):
			while d and d[0][1] < j:
				d.popleft()
		n = len(nums)
		ans = -math.inf
		start = 0
		i = 0
		while i < n:
			smallpush(sd, i)
			largepush(ld, i)
			if abs(ld[0][0] - sd[0][0]) <= limit:
				ans = max(ans, i - start + 1)
			else:
				while abs(ld[0][0] - sd[0][0]) > limit:
					if ld[0][1] == start:
						ld.popleft()
					if sd[0][1] == start:
						sd.popleft()
					start += 1
				ans = max(ans, i - start + 1)
			i += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		(maxd, mind) = (deque(), deque())
		(res, j) = (0, 0)
		for i in range(len(nums)):
			while len(maxd) > 0 and nums[maxd[-1]] < nums[i]:
				maxd.pop()
			while len(mind) > 0 and nums[mind[-1]] > nums[i]:
				mind.pop()
			maxd.append(i)
			mind.append(i)
			while j < i and len(maxd) > 0 and (len(mind) > 0) and (nums[maxd[0]] - nums[mind[0]] > limit):
				if j == maxd[0]:
					maxd.popleft()
				if j == mind[0]:
					mind.popleft()
				j += 1
			res = max(res, i - j + 1)
		return res


from collections import deque

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		lo = i = ans = 0
		(minq, maxq) = (deque(), deque())
		while i < len(nums):
			while minq and minq[-1][1] >= nums[i]:
				minq.pop()
			while maxq and maxq[-1][1] <= nums[i]:
				maxq.pop()
			minq.append((i, nums[i]))
			maxq.append((i, nums[i]))
			if maxq[0][1] - minq[0][1] > limit:
				lo += 1
				if lo > minq[0][0]:
					minq.popleft()
				if lo > maxq[0][0]:
					maxq.popleft()
			else:
				ans = max(ans, i - lo + 1)
				i += 1
		return ans


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		max_q = deque()
		min_q = deque()
		l = r = 0
		ans = 0
		while r < len(nums):
			num = nums[r]
			while max_q and nums[max_q[-1]] <= num:
				max_q.pop()
			while min_q and nums[min_q[-1]] >= num:
				min_q.pop()
			max_q.append(r)
			min_q.append(r)
			while nums[max_q[0]] - nums[min_q[0]] > limit:
				l += 1
				if l > max_q[0]:
					max_q.popleft()
				if l > min_q[0]:
					min_q.popleft()
			ans = max(ans, r - l + 1)
			r += 1
		return ans


import heapq

class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		if not nums:
			return 0
		max_len = 1
		(i, j) = (0, 0)
		min_heap = []
		max_heap = []
		max_n = min_n = nums[0]
		while i <= j and j < len(nums):
			if max_n - min_n <= limit:
				max_len = max(max_len, j - i + 1)
				j += 1
				if j == len(nums):
					continue
				if nums[j] > max_n:
					max_n = nums[j]
					heapq.heappush(min_heap, (nums[j], j))
				elif nums[j] < min_n:
					min_n = nums[j]
					heapq.heappush(max_heap, (-nums[j], j))
				else:
					heapq.heappush(min_heap, (nums[j], j))
					heapq.heappush(max_heap, (-nums[j], j))
			else:
				if nums[i] == max_n:
					while True:
						(max_n, s) = heapq.heappop(max_heap)
						if s > i:
							max_n *= -1
							break
				elif nums[i] == min_n:
					while True:
						(min_n, t) = heapq.heappop(min_heap)
						if t > i:
							break
				i += 1
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		(VALUE, INDEX) = (0, 1)
		left = 0
		(min_h, max_h) = ([], [])
		max_len = 0
		for (right, num) in enumerate(nums):
			heappush(min_h, (num, right))
			heappush(max_h, (-num, right))
			while -max_h[0][VALUE] - min_h[0][VALUE] > limit:
				if max_h[0][INDEX] < min_h[0][INDEX]:
					left = heappop(max_h)[INDEX] + 1
				else:
					left = heappop(min_h)[INDEX] + 1
				while min_h[0][INDEX] < left:
					heappop(min_h)
				while max_h[0][INDEX] < left:
					heappop(max_h)
			max_len = max(max_len, right - left + 1)
		return max_len


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		from heapq import heappop, heappush
		res = j = 0
		m = []
		n = []
		for i in range(len(nums)):
			x = nums[i]
			heappush(m, (-x, i))
			heappush(n, (x, i))
			while abs(-m[0][0] - n[0][0]) > limit:
				j = min(m[0][1], n[0][1]) + 1
				while j > m[0][1]:
					heappop(m)
				while j > n[0][1]:
					heappop(n)
			res = max(res, i - j + 1)
		return res


class Solution:

	def longestSubarray(self, nums: List[int], limit: int) -> int:
		maxq = deque()
		minq = deque()
		k = 0
		for i in nums:
			while maxq and i > maxq[-1]:
				maxq.pop()
			while minq and i < minq[-1]:
				minq.pop()
			maxq.append(i)
			minq.append(i)
			if maxq[0] - minq[0] > limit:
				if maxq[0] == nums[k]:
					maxq.popleft()
				if minq[0] == nums[k]:
					minq.popleft()
				k += 1
		return len(nums) - k