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

Difficulty: interview

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)
            # print(l, r, maxH, minH)
            ans = max(ans, r-l+1)
        return ans

# https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/721619/Python-Rust-Sliding-Window-and-Deque
'''
The problem description states that we need to find the window with the largest size that has max-min<=limit
This is clearly a sliding window problem. The brute force solution is to start from each index, keep on expanding, and once the max-min is larger than limit, we break. O(n^2)

Can we do better? Well, we can actually use a classic technique in sliding window problems where we keep on expanding the window from the right until the window is no longer valid.
Once the window is invalid we keep on contracting it from the left until it becomes valid again. (Just like in the famous \"Longest Substring Without Repeating Characters\" problem.

Every iteration we need to answer the question, what is our current min and max? this leads us to using two heaps where one of them is a min heap and the other is a max heap.

Every iteration we push the new number to both heaps and then keep on popping from the min and max heaps until we're sure that we've maintained the invariant maxHeap[0] - minHeap[0] <= limit.
We do O(N) pushes and pops from the heaps and each push/pop is O(logN) so we end up with an O(NlogN) solution.

Here is the code:
'''
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        minHeap, maxHeap = [], []
        left = maxLen = 0
        
        for right, num in enumerate(nums):
            heappush(minHeap, (num, right))
            heappush(maxHeap, (-num, right))
            
            while num - minHeap[0][0] > limit:
                left = max(left, heappop(minHeap)[1] + 1)
            while -maxHeap[0][0] - num > 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:
        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 #stores the index of the position where the array becomes invalid
        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:
        #naive method in n2
        #keep track of min and max
        #sliding window: only when exceed limit then contract window
        
        
        if not nums:
            return 0
        
        minDeque = collections.deque()
        maxDeque = collections.deque()
        maxlength = 0
        left = 0 
        right = 0
        
        while right< len(nums):#not equal sign
            while maxDeque and nums[right] > nums[maxDeque[-1]]:
                maxDeque.pop()
                #decreasign deque           
            maxDeque.append(right)
            
            while minDeque and nums[right] < nums[minDeque[-1]]:
                minDeque.pop()
            minDeque.append(right)
            
            #it won't be empty, because the \"curr\" element will always be valid
            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:
        import heapq
        mnq, mxq = [], []
        res = 0
        left = 0
        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]) + 1
                while mxq[0][1] < left:
                    heapq.heappop(mxq)
                while mnq[0][1] < left:
                    heapq.heappop(mnq)
            res = max(res, right - left + 1)
        return res

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):
            # print(start, end, ans)
            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:
        # we have to maintain two min/max heaps with both value and index
        # slide right if subarray is still valid
        # slide left until subarray is valid again: if min/max value's index is earlier than left, then pop it out
        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

# minMaxQueue:
# max 4 5
# min 4 3 3 2
#     queue: [1, 6, 8, 2, 2]

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

import heapq

# minMaxQueue:
# max 4 5
# min 4 3 3 2
#     queue: [1, 6, 8, 2, 2]

class Solution:
#     O(N) time | O(N) space
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        longest = 0
        mins = []
        maxs = []
        start = 0
        i = 0
        while i < len(nums): # O(N)
            x = nums[i]
            heapq.heappush(mins, (x, i)) # O()
            heapq.heappush(maxs, (-x, i)) # O()
            
            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:
    
        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:
            # a = A[j], A[i:j] is a candidate 
            # whose lenngth is j-i
            # whose max is M[0] and min is m[0]
            # if its max - min > limit we shrink the window
            # if max or min changed we pop M and m from the left
            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):
            # Maintain minDeque
            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:
            # print(\"i\", i, \"j\", j, \"max:\", -maxes[0][0], \"at idx\", maxes[0][1], \"min:\", mins[0][0], \"at idx\", mins[0][1])
            
            # advance j until difference exceeds limit
            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
                
                # lazily remove all values outside of the window
                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, nums: List[int], limit: int) -> int:
    #     start=0
    #     end=1
    #     result=1
    #     while end<len(nums):
    #         tmp=nums[end]
    #         flag=0
    #         for i in range(start,end):
    #             if abs(nums[i]-tmp)>limit:
    #                 flag=1
    #                 start=i
    #         if flag==0:
    #             if end-start+1>result:
    #                 result=end-start+1
    #             end+=1
    #         else:
    #             start+=1
    #     return result
    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


# lame implementation of random removal in min/max heaps, but i saw 
# phorum solutions about monotonic queues, quite interesting!

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, 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:
        # HEAP SLIDING WINDOW SOLUTION
        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:
                # we need to kick all the elments before left pointer
                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:
        # HEAP SLIDING WINDOW SOLUTION
        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, 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:
                # condition not satisfied, move left pointer ahead
                l = min(maxq[0][1], minq[0][1])+1
                #all values before left pointer are now useless
                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)
            #print(miheap,mxheap)
        return ans
            
            
        


class Solution:
    def longestSubarray(self, A: List[int], limit: int) -> int:
        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

# can get a o(n logn runtime)
# use min and max heaps 

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:
        
        res = 0
        maxq = []
        minq = []
        j = 0
        for i,n in enumerate(nums):
            heapq.heappush(maxq, [-n,i] )
            heapq.heappush(minq, [n,i] )
            
            while -maxq[0][0] - minq[0][0] > limit:
                ind = min( maxq[0][1], minq[0][1] )
                while maxq[0][1] <= ind:
                    heapq.heappop(maxq)
                while minq[0][1] <= ind:
                    heapq.heappop(minq)
                j = ind+1
            res = max(res, i - j +1 )
            
        return res
                
        
        
        
        
        
#         res = 0
        
#         i = 0
#         arr = [] # space O(res)
#         for n in nums:  # O(n) time
#             bisect.insort(arr, n) # O(res)
#             while arr[-1] - arr[0] > limit:
#                 ind = bisect.bisect_right(arr, nums[i])  # O( log res )
#                 arr.pop(ind-1)  # O(res)
#                 i += 1
#             res = max(res, len(arr))
            
#         return res
                
        
        
        
        
        


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        minq,maxq = [],[]
        l = 0
        res = 0
        for i in range(len(nums)):
            heapq.heappush(minq,[nums[i],i])
            heapq.heappush(maxq,[-nums[i],i])
            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,i-l+1)
        return res

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 len(nums) - i

import heapq
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:
        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:
        maxq=[]
        minq=[]
        res=0
        i=0
        for j,c in enumerate(nums):
            heapq.heappush(maxq,[-c,j])
            heapq.heappush(minq,[c,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:
#         minheap=[]
#         maxheap=[]
#         heapq.heapify(minheap)
#         heapq.heapify(maxheap)
#         length=1
#         i=0
#         j=1
#         heapq.heappush(minheap,[nums[0],0]) # add first element and its index
#         heapq.heappush(maxheap,[-nums[0],0])
#         while j < len(nums):
#             if nums[j]-minheap[0][0]<=limit and maxheap[0][0]*-1-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 nums[j]-minheap[0][0]>limit:
#                     ele,index=heapq.heappop(minheap)
#                     i=max(i,index + 1)
#                 while len(maxheap)>0 and -maxheap[0][0]-nums[j]>limit:
#                     ele,index=heapq.heappop(maxheap)
#                     i=max(i,index + 1)
#                 # i=maxindex+1   # update i and now  we are not concerned with element before ith index
#                 heapq.heappush(minheap,[nums[j],j]) # add  element and its index
#                 heapq.heappush(maxheap,[-nums[j],j])
#                 j=j+1
            
#         return length
        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:

        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

import heapq
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        
        # sliding window, but we only need to keep the min and max in this window along with the index. at the same time, we set a variable, to check what is the window starting point, we will do
        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 -min_heap[0][1] < start:
            #     heapq.heappop(min_heap)
            # while -max_heap[0][1] < start:
            #     heapq.heappop(max_heap)
           
            ### bug bug here: 加入出现现在的number导致超过了limit，那么你需要一直移动自动你找到一个index；
            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

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
# Solution 1: Use two heaps
# Time O(NogN)
# Space O(N)


        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

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: # Need to know the min and max
                # Make it valid!
                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

'''
1. example: [8,2,4,7]

- Subarrays can be created by taking one element at a time and moving forward
- difference can be found by finding the difference between two elements in the array. 



'''

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:
        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([]) # non-descreasing
    
    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([]) # non-increasing
    
    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):
            
            # push  
            minQ.push(nums[ptr2], ptr2)
            maxQ.push(nums[ptr2], ptr2)
            
            # print (ptr1, ptr2, minQ.queue, maxQ.queue)
            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])
            
                # print ('*', ptr1, ptr2, minQ.queue, maxQ.queue)
            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)
            # print(min_queue, max_queue)
            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, 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:
        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
            
                
            
            
            
                
                


from collections import deque
class Solution:
    def longestSubarray(self, nums, limit):
        maxQ, minQ = deque(), deque()
        i = 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()
                elif minQ[0] == nums[i]: minQ.popleft()
                i += 1
        return len(nums) - i


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:
        # dp = [[0 for _ in range(len(nums))] for _ in range(len(nums))]
        # result = 1
        # for i in range(len(nums)-2, -1, -1):
        #     for j in range(i+1, len(nums)):
        #         dp[i][j] = max(dp[i][j-1], dp[i+1][j] ,abs(nums[i] - nums[j]))
        #         # print(dp[i][j])
        #         if dp[i][j] <= limit:
        #             result = max(result, j - i + 1)
        # return result
    
        maxq, minq = [], []
        res = i = 0
        for j, a in enumerate(nums):
            heapq.heappush(maxq, [-a, j])
            heapq.heappush(minq, [a, j])
            # print(maxq, minq)
            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)
            # print(maxq)
            # print(minq)
        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
            
                
            
            
            
                
                


import heapq
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        
        # sliding window, but we only need to keep the min and max in this window along with the index. at the same time, we set a variable, to check what is the window starting point, we will do
        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 -min_heap[0][1] < start:
                heapq.heappop(min_heap)
            while -max_heap[0][1] < start:
                heapq.heappop(max_heap)
            # if num == 96:
            #     print(num)
            
            ### bug bug here: 加入出现现在的number导致超过了limit，那么你需要一直移动自动你找到一个index；
            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)
                # if num == min_heap[0][0]:
                #     start = -max_heap[0][1]+1
                # if num == -max_heap[0][0]:
                #     start = -min_heap[0][1]+1
  
            res = max(res, i - start + 1)
            #print(i, start, res) 
            #if num == 3:
                #print(sorted(max_heap))
                #print(sorted(min_heap))
        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:
        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

from collections import deque
class Solution:
    def longestSubarray(self, nums, limit):
        maxQ, minQ = deque(), deque()
        i = 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
        return len(nums) - i

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
   
        # while left <= right and right < len(nums):
        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:

        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
   
        # while left <= right and right < len(nums):
        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
            right += 1
        return max_len


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
            #print(diff, left, right)
            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]) # add first element and its index
        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)
                # i=maxindex+1   # update i and now  we are not concerned with element before ith index
                heapq.heappush(minheap,[nums[j],j]) # add  element and its index
                heapq.heappush(maxheap,[-nums[j],j])
                j=j+1
            
        return length
#         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] - list(heap_min)[0][0] > limit:
#                 value, idx = heapq.heappop(heap_min)
#                 begin = max(begin, idx + 1)
            
#             while len(heap_max) > 0 and (list(heap_max)[0][0]*-1) - 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


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:  # decrease
                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:  # increase
                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
        #n = len(nums)
        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:
                #max_l = max(max_l, end-start)
                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:
        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
                


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])  # Used to track maximum number
        min_stack = collections.deque([0])  # Used to track minimum number
        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, 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 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
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
#         if not nums:
#             return 0
#         if len(nums) == 1: 
#             return 1
        
#         l, r = 0, 1
#         res = 1
#         min_in_window = nums[0]
#         max_in_window = nums[0]
#         while r < len(nums):
#             min_in_window = min(min_in_window, nums[r])
#             max_in_window = max(max_in_window, nums[r])
#             if abs(min_in_window - max_in_window) <= limit:
#                 res = max(res, r - l + 1)
#             else:
#                 while l <= r and l < len(nums) - 1 and nums[l] == nums[l+1]:
#                     l += 1
#                 if nums[l] == min_in_window:
#                     min_in_window = min(nums[l+1:r+1])
#                 if nums[l] == max_in_window:
#                     max_in_window = max(nums[l+1:r+1])
#                 l += 1
#             r += 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:
        minheap=[]
        maxheap=[]
        heapq.heapify(minheap)
        heapq.heapify(maxheap)
        length=1
        i=0
        j=1
        heapq.heappush(minheap,[nums[0],0]) # add first element and its index
        heapq.heappush(maxheap,[-nums[0],0])
        while j < len(nums):
            if nums[j]-minheap[0][0]<=limit and maxheap[0][0]*-1-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)
                # i=maxindex+1   # update i and now  we are not concerned with element before ith index
                heapq.heappush(minheap,[nums[j],j]) # add  element and its index
                heapq.heappush(maxheap,[-nums[j],j])
                j=j+1
            
        return length
#         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] - list(heap_min)[0][0] > limit:
#                 value, idx = heapq.heappop(heap_min)
#                 begin = max(begin, idx + 1)
            
#             while len(heap_max) > 0 and (list(heap_max)[0][0]*-1) - 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


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:
        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]
            #print(i,j,mn,mx)
            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:
        # TC is O(N^2)
        start = 0
        L = []
        maxlen = 0

        for end, item in enumerate(nums):
            # insert the current item in appropriate position
            bisect.insort(L, item) # insort is O(N)
            # if the difference between start and end is more than expected, keep popping the start indexes
            while L[-1] - L[0] > limit:
                #*****bisect will give you the index but it is ALWAYS +1
                idx = bisect.bisect(L, nums[start]) - 1 # logN TC
                L.pop(idx) # pop that shit and recompute max-min difference again
                start += 1
            maxlen = max(maxlen, end-start+1)
        return maxlen'''

    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # insort was expesive in above O(N) so use 2 heaps to maintain max and min
        maxheap = []
        minheap = []
        start = 0
        maxlen = 0
        
        for end, item in enumerate(nums):
            heapq.heappush(minheap, (item, end))
            heapq.heappush(maxheap, (-item, end))
            #print(minheap, maxheap)
            while maxheap and minheap and -maxheap[0][0]-minheap[0][0]>limit:
                #print()
                #print('heap', minheap, maxheap)
                # find the minimum index of max or min
                start = min(maxheap[0][1], minheap[0][1]) + 1
                # it will be either of min or max, make sure to pop shit just above start so we dont have the max and min item below start
                while maxheap[0][1] < start:
                    heapq.heappop(maxheap)
                while minheap[0][1] < start:
                    heapq.heappop(minheap)
                #print('heap', minheap, maxheap)
            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]: # 允许相同元素存在，这样的话滑动窗口pop的时候才能正确的pop完，否则会出现过早的pop完但left还没跟上的情况
                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)
            # print(left, right, res, inc, dec, )
        return res

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # asc stack
        # desc stack
        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, 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:
        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
        
        #nums.sort()
        #nums = [8,2,4,7]
        
        maxL=0
        beg=0
        #end=1
        '''
        while beg<len(nums)-1:
            #mx=max(nums[beg:(end+1)])
            #mn=min(nums[beg:(end+1)])
            while end<len(nums) and max(nums[beg:(end+1)])-min(nums[beg:(end+1)])<=limit:
                maxL=max(maxL, end-beg+1)
                end+=1
            beg+=1
            end=beg+1
        return maxL
        '''
        minQueue, maxQueue = collections.deque([]), collections.deque([])
        #minQueue, maxQueue=[], []
        #minQueue increasing, maxQueue decreasing
        
        #minQueue.append(nums[beg])
        #maxQueue.append(nums[beg])
        end=beg  
        while end<len(nums):
            
            #need while loop because if minQueue=[3,4,7], nums[end]=2
            #then since minQueue must be increasing and need to append nums[end]=2
            #so must remove 3,4, and 7
            while len(minQueue)>0 and nums[end]<minQueue[-1]:
                minQueue.pop()
            minQueue.append(nums[end]) #[2]
            
            #print(\" min: \", minQueue)
            
            while len(maxQueue)>0 and nums[end]>maxQueue[-1]:
                maxQueue.pop()
            maxQueue.append(nums[end]) #[7,2]
            
            
            if maxQueue[0]-minQueue[0]<=limit:
                maxL=max(maxL, end-beg+1)
            else:
                if maxQueue[0]==nums[beg]:
                    maxQueue.popleft()  #[1]
                    #maxQueue.pop(0)  #[1]
                if minQueue[0]==nums[beg]:
                    minQueue.popleft()  #[1]
                    #minQueue.pop(0)  #[1]
                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
                    
            
                
    


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        import collections
        min_deque = deque() 
        max_deque = deque()
        l = 0 
        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)
            
            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
                l += 1
                if l > min_deque[0]:
                    min_deque.popleft()
                if l > max_deque[0]:
                    max_deque.popleft()
            
            ans = max(ans, r - l + 1)
            r += 1
                
        return ans

import heapq
# import collections

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
                    
#         maxq = collections.deque()
#         minq = collections.deque()
#         res = i = 0
        
#         for j in range(len(nums)):
#             while maxq and nums[maxq[-1]] < nums[j]: maxq.pop()
#             while minq and nums[minq[-1]] > nums[j]: minq.pop()
            
#             maxq.append(j)
#             minq.append(j)
            
#             while nums[maxq[0]] - nums[minq[0]] > limit:
#                 i = min(maxq[0], minq[0]) + 1
#                 while i > maxq[0]: maxq.popleft()
#                 while i > minq[0]: minq.popleft()
            
#             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:
        
        maxd = collections.deque()
        mind = collections.deque()
        i = 0
        for a in nums:
            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] == nums[i]: maxd.popleft()
                if mind[0] == nums[i]: mind.popleft()
                i += 1
        return len(nums) - i

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

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return 1
        cur_max = nums[0]
        cur_min = nums[0]
        l=0
        r=1
        max_l = 1
        
        while l<=r and r<len(nums):
            cur_max = max(cur_max, nums[r])
            cur_min = min(cur_min, nums[r])
            if cur_max-cur_min <=limit:
                max_l = max(max_l, r-l+1)
            else:
                if nums[l] == cur_max:
                    cur_max = max(nums[l+1:r+1])
                if nums[l] == cur_min:
                    cur_min = 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:
        # we keep two pointers and we keep track of min and max between those pointers
        # if the new number being added is having difference from both min and max within the range we increase j and update min and max if necessary else we increase i till we get the difference less than target while changing i and also we keep on updating the min and max
        # it can mark the beginning of a new sub array
        # however if we can make this update faster constant time and at max we need to increase i from i to j by deleting each number then also it is in worse case O(nk) instead of linear we can save sometime
        # we do not need indices and so we can use SortedList instead of SortedDict to make processing of finding min and max after changing i faster
        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
        
        '''
        s = SortedList()
        # we keep on adding new values to the sortedList and when we get max - min greater than target then we keep on removing values from the list till the sorted list becomes valid again
        # thus we have a solution with O(nlogn) complexity and faster than the one with sortedDict although it is having same complexity
        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
        '''
        # for the following approach also the time limit gets exceeded because although operations on dictionary are O(logn) we are doing them for more number of times then expected
        '''
        # i.e. if min is our problem then we need to increase i till we find new min 
        # i.e we need to start from i = i + max_index of current_min
        # and if max is our problem then we need to increase i till we find new max
        # i.e we need to start from i = i + max_index of current_max
        # and if both are a problem then we need to increase i till max when both are changed
        # this we can do if we use a hashmap mapping each value from i to j with its max index in the array we do not care for intermediate indices
        max_length = -float('inf')
        mapping = SortedDict()
        Min = nums[0]
        Max = nums[0]
        mapping[Min] = 0
        i = 0
        while i < len(nums):
            j = i
            # print('a',i,j,Max,Min)
            while j < len(nums) and abs(nums[j] - Min) <= limit and abs(nums[j] - Max) <= limit:
                Max = max(Max,nums[j])
                Min = min(Min,nums[j])
                # we are just concerned with the max value
                mapping[nums[j]] = j
                j += 1
                max_length = max(max_length,j - i)
                
            # print('b',i,j,Min,Max)
            if j >= len(nums)-1:
                break
            else:
                mapping[nums[j]] = j
                while i <= j and (abs(nums[j] - Min) > limit or abs(nums[j] - Max) > limit):
                    if abs(nums[j] - Min) > limit and abs(nums[j] - Max) > limit:
                        i = max(i,max(mapping[Min],mapping[Max]) + 1)
                        del mapping[Max]
                        if Min in mapping.keys():
                            del mapping[Min]

                    elif abs(nums[j] - Min) > limit:
                        i = max(i,mapping[Min] + 1)
                        del mapping[Min]
                        
                    elif abs(nums[j] - Max) > limit:
                        i = max(i,mapping[Max] + 1)
                        del mapping[Max]
                    # after each update we need to update min and max and the following steps will take O(n)
                    Min = mapping.peekitem(0)[0]
                    Max = mapping.peekitem()[0]
                    while mapping[Min] < i:
                        del mapping[Min]
                        Min = mapping.peekitem(0)[0]
                    while mapping[Max] < i:
                        del mapping[Max]
                        Max = mapping.peekitem()[0]
                    
                # print(mapping)
                # print('c',i,j,Max,Min)
        return max_length
        
        '''
        # for the following approach time limit gets exceeded
        '''
        max_length = -float('inf')
        Min = nums[0]
        Max = nums[0]
        i = 0
        while i < len(nums):
            j = i 
            #print('a',i,j,Max,Min)
            while j < len(nums) and abs(nums[j] - Min) <= limit and abs(nums[j] - Max) <= limit:
                Max = max(Max,nums[j])
                Min = min(Min,nums[j])
                j += 1
                max_length = max(max_length,j - i)
            #print('b',i,j,Max,Min,len(nums))
            if j >= len(nums)-1:
                break
            else:
                while i < j and nums[i] != Min and nums[i] != Max:
                    i += 1
                while i < j and (abs(nums[j] - Min) > limit or abs(nums[j] - Max) > limit):
                    i += 1
                    #print(i)
                    Min = min(nums[i:j+1])
                    Max = max(nums[i:j+1])
                    #print('c',i,j,Max,Min)
        return max_length
        '''            
        
        
        


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:
        '''
        Find the longest non-empty subarray s where max(s) - min(s) <= limit
        '''
        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:
                # Fast forward i
                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:

        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
        
        while left <= right and right < 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
            right += 1
        return max_len


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:
                # recompute min and max
                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

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 minQ and val - nums[minQ[0]] > limit:
                last = max(last, minQ.popleft())
            res = max(res, i - last)
            while maxQ and val >= nums[maxQ[-1]]:
                maxQ.pop()
            maxQ.append(i)
            while minQ and val <= nums[minQ[-1]]:
                minQ.pop()
            minQ.append(i)
        return res
    
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 minQ and val - nums[minQ[0]] > limit:
                last = max(last, minQ.popleft())
            #res = max(res, i - last)
            if i - last > res: res = i - last
            while maxQ and val >= nums[maxQ[-1]]:
                maxQ.pop()
            maxQ.append(i)
            while minQ and val <= nums[minQ[-1]]:
                minQ.pop()
            minQ.append(i)
        return res

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:
        
        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])
            
            print(currmax,currmin)
            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:
        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:
            # Remove elements from the min and max that are stale
            while min_deque and min_deque[0][1] < i: min_deque.popleft()
            while max_deque and max_deque[0][1] < i: max_deque.popleft()
                
            # Keep adding elements if the invariant is true    
            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):
        # Keep popping from the right until the new value is smaller
        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:
        # min_stack = []
        # max_stack = []
        # for i, number in enumerate(nums):
        #     _index = i
        #     while max_stack and number > max_stack[-1][0]:
        #         _, _index = max_stack.pop()
        #     max_stack.append((number, _index))
        #     _index = i
        #     while min_stack and number < min_stack[-1][0]:
        #         _, _index = min_stack.pop()
        #     min_stack.append((number, _index))
        # longest = -1
        # start_index = len(nums) - 1
        # print(max_stack)
        # print(min_stack)
        # while max_stack[-1][0] - min_stack[-1][0] <= limit:
        #     longest = max(
        #         longest,
        #         abs(max_stack[-1][1] - min_stack[-1][1])
        #     )
        #     if max_stack[-1][1] > min_stack[-1][1]:
        #         max_stack.pop()
        #     else:
        #         min_stack.pop()
        # return longest
            
            
        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
                else:
                    if 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: 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)
    
    
    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:
        # [8, 2, 4, 7] limit = 4
        # want to keep track of max and min elements + indexes
        # thinking of a sliding window approach
        # 8, 8 -> 8, 2 -> 2, 4 -> 2, 7 -> end
        # difference between i and j + 1
        # [10, 1, 2, 4, 7, 2], limit = 5
        # 10, 10 -> 10, 1 -> 1, 2 -> 1, 4 -> 1, 7 -> 2, 7 -> 2, 2 -> end
        # turns out i need a list of max and min elements + indexes
        # [8, 11, 5, 7, 9, 10, 8, 7, 6];
        # (8, 11) -> (11, 5) -> 
        # The list of max elements must contain elements in window, descending order
        # The list of min elements must contain elements in window, ascending order
        
        # (6, 8) (7, 7) (9, 6)
        # (9, 6)
        # i = 3, j = 10
        # res = 6
        
        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):
            # 13
            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
                    # print(r, Q, Q_2)
                    result = max(result, r)

                ni = i
                while len(Q) and v <= Q[-1][1]:
                    mp, vp = Q.pop()  # <=============== change i !!!
                    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()  # <=============== change i !!!
                    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)
           
            
            #print (st , 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
            #print(ans)
        
        return ans
                


from heapq import heappush,heappop
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        i = j = best = 0
        minHeap, maxHeap = [], []

        while i < len(nums) and 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


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)
            # print(\"iteration\")
            # print(r)
            # print(ans)
            # print(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

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

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)
            #print(maxd,mind,sol,left)
        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:
        # heap maps
        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
        
        
        
        
        
        '''
        # using heaps
        maxq, minq = [], []
        n = len(nums)
        
        r = 0
        for l in range(n):
            heapq.heappush(maxq, (-nums[i], l))
            heapq.heappush(minq, (nums[i], l))
            
            
            while abs(maxq[0][0] + minq[0][0]) <= limit:
                while max[0][0]
        '''

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]) # add first element and its index
#         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)
#                 heapq.heappush(minheap, [nums[end],end])
#                 heapq.heappush(maxheap, [-nums[end],end])
#                 end+=1
#             else:
#                 while len(minheap) and abs(minheap[0][0] - nums[end]) > limit:
#                     ele,idx = heapq.heappop(minheap)
#                     next_idx = max(next_idx, idx)
#                 while len(maxheap) 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
        
        minheap=[]
        maxheap=[]
        heapq.heapify(minheap)
        heapq.heapify(maxheap)
        length=1
        i=0
        j=1
        heapq.heappush(minheap,[nums[0],0]) # add first element and its index
        heapq.heappush(maxheap,[-nums[0],0])
        maxindex=0
        while i<=j and j<=len(nums)-1:
            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)
                    maxindex=max(maxindex,index)
                while len(maxheap)>0 and abs(-maxheap[0][0]-nums[j])>limit:
                    ele,index=heapq.heappop(maxheap)
                    maxindex=max(maxindex,index)
                i=maxindex+1   # update i and now  we are not concerned with element before ith index
                heapq.heappush(minheap,[nums[j],j]) # add  element and its index
                heapq.heappush(maxheap,[-nums[j],j])
                j=j+1
            
        return length
        
#         def isValid(int_diff, j, max_value, min_value, limit, nums):
#             max_boundary = abs(max_value - nums[j])
#             min_boundary = abs(min_value - nums[j])
#             return int_diff <= limit and max_boundary <= limit and min_boundary <= limit
        
#         def find_error(int_diff,i, j, max_value, min_value, limit, nums,cache):
#             max_boundary = abs(max_value - nums[j])
#             min_boundary = abs(min_value - nums[j])
            
#             if int_diff > limit: return i
#             if max_boundary > limit: return cache[max_value]
#             if min_boundary > limit: return cache[min_value]
            
#         output = 1
#         i = 0
#         idx = 0
#         cache = defaultdict(int)
#         while i < len(nums) and idx < len(nums)-1:
#             min_value = float('inf')
#             max_value = float('-inf')
#             cache[min_value] = i
#             cache[max_value] = i
#             for j in range(i,len(nums)):
                
#                 int_diff = abs(nums[j] - nums[i])
#                 temp_min = min_value
#                 temp_max = max_value
#                 min_value = min(min_value, nums[j])
#                 max_value = max(max_value, nums[j])
#                 if temp_min != min_value:
#                     cache[min_value] = j
#                 if temp_max != min_value:
#                     cache[max_value] = j
#                 if isValid(int_diff, j, max_value, min_value, limit, nums):
#                     output = max(output, (j - i) + 1)
#                 else:
#                     i = find_error(int_diff, i, j, max_value, min_value, limit, nums,cache) + 1
                    
#                     break
#                 idx = j
#         return output
                
                
        
            


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

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
        
        # The top of maxStack is the position of the max element currently
        # being used by the subarray.
        # As the algorithm (which grows that subarray righwards) discovers new elements that
        # are incompatible with the current max, we ditch this current max and check for validity
        # with the next max. Thus the maxStack contains a sequence of positions of the next
        # possible. This also means the values must be decreasing (think about why).
        maxStack = []
        
        # Same for minStack, but for mins.
        minStack = []
        result = 1
        
        # The subarray goes from leftPos to i.
        leftPos = 0
        for i in range(0, len(nums)):
            # if nums[i] exceeds the max, keep popping off the max and try
            # again with the next max. Naturally, we update leftPos since
            # the leftmost valid position is moving until we find a valid max
            while maxStack and nums[i] < nums[maxStack[0]] - limit:
                leftPos = max(leftPos, maxStack.pop(0) + 1)
            
            # We do the same for minimum
            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
                
            # recall: maxStack[0] must always be the currently used maximum. And the next elements
            # contain the next one to try if we have to ditch maxStack[0]
            # This means if nums[i] is larger than
            # ALL the elements in maxStack, then of course nums[i] should become our current max. To do
            # that we pop away the entirety of maxStack and push i onto it. But if nums[i] is larger
            # than some elements of maxStack, we pop away only those elements and then stop. Then we push
            # i to the end because it represents a possible next maximum that can be used in the future
            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

#TRY 8/19/2020 
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)
            
            # max_val = nums[max_deque[0]]
            # min_val = nums[min_deque[0]]
            # limit_break = abs(max_val - min_val)
            while abs(nums[max_deque[0]] - nums[min_deque[0]]) > limit: #limit has been broken. 
#                 limit_break -= nums[start]
                start += 1 #shrink the window.
                if start > min_deque[0]: 
                    min_deque.popleft()
                if start > max_deque[0]:
                    max_deque.popleft()
                
             
            
            #Get the best window length so far.        
            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:
#         # sanity check
#         if nums is None or len(nums) <= 1 or limit < 0:
#             return 1
        
#         # sliding window approach in O(n) time
#         max_len, l, r = 0, 0, 0
        
#         # notice that, the only absolute difference we need to check is the 
#         # maximum possible absolute difference since it ensures there are no
#         # other absolute differences that can be bigger than @limit
#         max_val, min_val = 0, 0
        
#         # dequeu method of keeping a local min and max over a sliding window in 
#         # amortized O(1) time 
#         # reference: https://www.nayuki.io/page/sliding-window-minimum-maximum-algorithm
#         min_dq, max_dq = [], []
        
#         while r < len(nums):
#             val = nums[r] 
            
#             # update min_dq
#             while len(min_dq) > 0 and val < min_dq[-1]:
#                 min_dq.pop()
#             min_dq.append(val)
            
#             # update max_dq
#             while len(max_dq) > 0 and val > max_dq[-1]:
#                 max_dq.pop()
#             max_dq.append(val)

#             max_val = max_dq[0]
#             min_val = min_dq[0]
            
#             diff = abs(max_val - min_val)
            
#             # note that we do not have to worry about the left pointer passing the right one
#             if diff > limit:
#                 # recalculate min and max values of window by updating dequeues
#                 check = nums[l]
#                 if check == min_dq[0]:
#                     min_dq.pop(0)
#                 if check == max_dq[0]:
#                     max_dq.pop(0)
                
#                 # shrink window
#                 l += 1
            
#             # expand window
#             max_len = max(max_len, r - l + 1)
#             r += 1
        
#         return max_len  


# class Solution:
#     def longestSubarray(self, nums: List[int], limit: int) -> int:
#         #int array nums
#         #int limit 
#         #ret longest non-empty subarray s.t 
#         #the absolute diff betweeen any two elemetns of the subarray is <= limit 
        
#         start = 0
#         end = 0 
        
#         min_ele = float('inf')
#         max_ele = float('-inf')
#         sub_array = []
        
#         contig_sub = float('-inf')
#         #currently start at zero but let's see if we can try to start at the end maybe? 
#         while end < len(nums):
#             sub_array = nums[start:end + 1]
#             limit_breaker = abs(max(sub_array) - min(sub_array))
            
#             while limit_breaker > limit: #You are too much :'( 
#                 tmp = start 
            
#                 limit_breaker -= nums[tmp]
#                 # start += 1 #This is too early because once we've subtracted we're using it 
#                 #This means that start wil lbe < 1 for contig sub potentially. 
                
#             if limit_breaker <= limit: #You are okay. 
#                 contig_sub = max(contig_sub, end - start + 1)
#             end += 1
        
#         return contig_sub

# class Solution:
#     def longestSubarray(self, nums: List[int], limit: int) -> int:
#         #Queues to take the min and the max of our subarray so far.
#         min_deque, max_deque = deque(), deque()
#         l = r = 0
#         ans = 0
#         while r < len(nums):
#             #Min_deque has the minimum value position and check if there are better ones 
#             while min_deque and nums[r] <= nums[min_deque[-1]]:
#                 min_deque.pop()
#             min_deque.append(r)
            
#             #Max_deque has the maximum value position and check if there are better ones 
#             while max_deque and nums[r] >= nums[max_deque[-1]]:
#                 max_deque.pop()
#             max_deque.append(r)
            
#             #Limit break the limit? 
#             #If it does then we can find the next one. 
#             while nums[max_deque[0]] - nums[min_deque[0]] > limit:
#                 l += 1
#                 #if the next position is > than our current one than we know it's no longer a part of the subarray.
#                 if l > min_deque[0]:
#                     min_deque.popleft()
#                 if l > max_deque[0]:
#                     max_deque.popleft()
            
#             ans = max(ans, r - l + 1)
#             r += 1
                
#         return ans
                         


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 minQ and val - nums[minQ[0]] > limit:
                last = max(last, minQ.popleft())
            #res = max(res, i - last)
            if i - last > res: res = i - last
            while maxQ and val >= nums[maxQ[-1]]:
                maxQ.pop()
            maxQ.append(i)
            while minQ and val <= nums[minQ[-1]]:
                minQ.pop()
            minQ.append(i)
        return res

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:
        '''
        根据要求，子串任意两个数之间的差要小于等于limit
        所以利用递增栈与递减栈记录子串的最大与最小值
        maxs[0]-mins[0] 作为子数组的最大maxdiff
        '''
        n=len(nums)
        maxs=[]  #递减栈
        mins=[]  #递增栈
        #maxs[0]-mins[0] 作为子数组的最大maxdiff
        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:
        # we keep two pointers and we keep track of min and max between those pointers
        # if the new number being added is having difference from both min and max within the range we increase j and update min and max if necessary else we increase i till we get the difference less than target while changing i and also we keep on updating the min and max
        # it can mark the beginning of a new sub array
        # however if we can make this update faster constant time and at max we need to increase i from i to j by deleting each number then also it is in worse case O(nk) instead of linear we can save sometime
        # we do not need indices and so we can use SortedList instead of SortedDict to make processing of finding min and max after changing i faster
        s = SortedList()
        # we keep on adding new values to the sortedList and when we get max - min greater than target then we keep on removing values from the list till the sorted list becomes valid again
        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
        
        
        
        
        # for the following approach also the time limit gets exceeded because although operations on dictionary are O(logn) we are doing them for more number of times then expected
        '''
        # i.e. if min is our problem then we need to increase i till we find new min 
        # i.e we need to start from i = i + max_index of current_min
        # and if max is our problem then we need to increase i till we find new max
        # i.e we need to start from i = i + max_index of current_max
        # and if both are a problem then we need to increase i till max when both are changed
        # this we can do if we use a hashmap mapping each value from i to j with its max index in the array we do not care for intermediate indices
        max_length = -float('inf')
        mapping = SortedDict()
        Min = nums[0]
        Max = nums[0]
        mapping[Min] = 0
        i = 0
        while i < len(nums):
            j = i
            # print('a',i,j,Max,Min)
            while j < len(nums) and abs(nums[j] - Min) <= limit and abs(nums[j] - Max) <= limit:
                Max = max(Max,nums[j])
                Min = min(Min,nums[j])
                # we are just concerned with the max value
                mapping[nums[j]] = j
                j += 1
                max_length = max(max_length,j - i)
                
            # print('b',i,j,Min,Max)
            if j >= len(nums)-1:
                break
            else:
                mapping[nums[j]] = j
                while i <= j and (abs(nums[j] - Min) > limit or abs(nums[j] - Max) > limit):
                    if abs(nums[j] - Min) > limit and abs(nums[j] - Max) > limit:
                        i = max(i,max(mapping[Min],mapping[Max]) + 1)
                        del mapping[Max]
                        if Min in mapping.keys():
                            del mapping[Min]

                    elif abs(nums[j] - Min) > limit:
                        i = max(i,mapping[Min] + 1)
                        del mapping[Min]
                        
                    elif abs(nums[j] - Max) > limit:
                        i = max(i,mapping[Max] + 1)
                        del mapping[Max]
                    # after each update we need to update min and max and the following steps will take O(n)
                    Min = mapping.peekitem(0)[0]
                    Max = mapping.peekitem()[0]
                    while mapping[Min] < i:
                        del mapping[Min]
                        Min = mapping.peekitem(0)[0]
                    while mapping[Max] < i:
                        del mapping[Max]
                        Max = mapping.peekitem()[0]
                    
                # print(mapping)
                # print('c',i,j,Max,Min)
        return max_length
        
        '''
        # for the following approach time limit gets exceeded
        '''
        max_length = -float('inf')
        Min = nums[0]
        Max = nums[0]
        i = 0
        while i < len(nums):
            j = i 
            #print('a',i,j,Max,Min)
            while j < len(nums) and abs(nums[j] - Min) <= limit and abs(nums[j] - Max) <= limit:
                Max = max(Max,nums[j])
                Min = min(Min,nums[j])
                j += 1
                max_length = max(max_length,j - i)
            #print('b',i,j,Max,Min,len(nums))
            if j >= len(nums)-1:
                break
            else:
                while i < j and nums[i] != Min and nums[i] != Max:
                    i += 1
                while i < j and (abs(nums[j] - Min) > limit or abs(nums[j] - Max) > limit):
                    i += 1
                    #print(i)
                    Min = min(nums[i:j+1])
                    Max = max(nums[i:j+1])
                    #print('c',i,j,Max,Min)
        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:
        # Use sortedList to maintain the max/min of the subarray 
        from sortedcontainers import SortedList
        wd = SortedList([nums[0]])  # window
        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)
                # extend right
                r += 1
                if r < len(nums):
                    wd.add(nums[r])
            else:
                # shrink left
                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


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
                
                
                
            
            
            
        
        


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):
            # print(l,r)
            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))
            # print(min_heap)
            # print(max_heap)
            # print(min_heap[0][0], max_heap[0][0])
            
            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:
                #print('here')
                if (min_heap[0][1] < max_heap[0][1]):
                    min_idx = min_heap[0][1] + 1
                    heapq.heappop(min_heap)
                    #print('min_idx', min_idx)
                else:
                    min_idx = max_heap[0][1] + 1
                    heapq.heappop(max_heap)
                    
            #print(min_heap[0][1], max_heap[0][1])
            #print(min_idx, i)
            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

# [10, 1, 2, 4, 7, 2]
# pqmax: [(-7, 4), (-4, 3), (-2, 2), (-1, 1), (-2, 5)]
# pqmin: [(2, 2), (2, 5), (7, 4), (10, 0), (4, 3)]
# end: 5
# start: 2

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


from collections import deque
class Solution:
    def longestSubarray(self, nums, limit):
        maxQ, minQ = deque(), deque()
        i = 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)
            while 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
    
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

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]]
            #print(i,j,diff,winMax,winMin)
            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
        
        # sliding window to calculate min-max range
        # extend window if range is within limit r -->
        # shrink window if range is off limit l -->
        # sliding window is a sorted subarray
        
        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)
            # print(max_q, min_q)
            # max_num = max_q[0]
            # min_num = min_q[0]
            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(abs(max_q[0]-min_q[0]) +1, ans) 
            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 and right index to take out the substring
        left = 0
        right = 1
        #let current max and min equal to the first number
        cur_max = cur_min = nums[0]
        #the max lense of the target substring is at least 1
        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
    
# time: O(n^2)
# space: O(n)


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
    


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        if len(nums) == 0:
            return 0
        dec_stack = [] # stores all the next largest value  (value, pos)
        inc_stack = [] # stores all the next min value (value, pos)
        max_interval = 1
        
        # two pointer expand and contract, including
        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
                # added new values update our stacks
                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]
            
            # now the interval does not fit the limit, contract
            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)#先append 当前数
                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:
        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:
        # print('start')
        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
            # print(len(sl))
        return best

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 = collections.deque()
        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.popleft()
                cur_max = max(sub_nums)
                cur_min = min(sub_nums)
        return  len(sub_nums)

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        #https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609701/Python-two-heap-solution
        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)
                elif 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:
        # 2:37
        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


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]) # add first element and its index
        heapq.heappush(maxheap,[-nums[0],0])
        maxindex=0
        while i<=j and j<=len(nums)-1:
            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)
                    maxindex=max(maxindex,index)
                while len(maxheap)>0 and abs(-maxheap[0][0]-nums[j])>limit:
                    ele,index=heapq.heappop(maxheap)
                    maxindex=max(maxindex,index)
                i=maxindex+1   # update i and now  we are not concerned with element before ith index
                heapq.heappush(minheap,[nums[j],j]) # add  element and its index
                heapq.heappush(maxheap,[-nums[j],j])
                j=j+1
            
        return length
            


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


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
    
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
        res = 0
        for j, val in enumerate(nums):
            while maxQ and val > nums[maxQ[-1]]: maxQ.pop()
            while minQ and val < nums[minQ[-1]]: minQ.pop()
            maxQ.append(j)
            minQ.append(j)
            if nums[maxQ[0]] - nums[minQ[0]] > limit:
                if maxQ[0] == i: maxQ.popleft()
                if minQ[0] == i: minQ.popleft()
                i += 1
            res = max(res, j - i + 1)
        return res

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_stack = []
        # max_stack = []
        # for i, number in enumerate(nums):
        #     _index = i
        #     while max_stack and number > max_stack[-1][0]:
        #         _, _index = max_stack.pop()
        #     max_stack.append((number, _index))
        #     _index = i
        #     while min_stack and number < min_stack[-1][0]:
        #         _, _index = min_stack.pop()
        #     min_stack.append((number, _index))
        # longest = -1
        # start_index = len(nums) - 1
        # print(max_stack)
        # print(min_stack)
        # while max_stack[-1][0] - min_stack[-1][0] <= limit:
        #     longest = max(
        #         longest,
        #         abs(max_stack[-1][1] - min_stack[-1][1])
        #     )
        #     if max_stack[-1][1] > min_stack[-1][1]:
        #         max_stack.pop()
        #     else:
        #         min_stack.pop()
        # return longest
            
            
        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:
                # print(self.calc_diff(-max_q[0][0], min_q[0][0]) )
                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)
                # print(start_index, value, q)
                # print(start_index, _index, value)
                while q and q[0][1] < start_index:
                    heappop(q)
            cur_longest_len = max(
                cur_longest_len,
                i - start_index + 1
            )
            # if cur_longest_len == 3:
            #     print(\"HERE\", start_index, i)
        # print(max_q)
        # print(min_q)
        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

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        
        maxheap, minheap = [(-nums[0], 0)], [(nums[0], 0)]
        
        l, res  = 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 - l + 1)
            else:
                
                while minheap and val - minheap[0][0] > limit:
                    v, index = heapq.heappop(minheap)
                    l = max(l, index + 1)
                while maxheap and -maxheap[0][0] - val > limit:
                    v, index = heapq.heappop(maxheap)
                    l = max(l, index + 1)
            
            heapq.heappush(minheap, (val, i))
            heapq.heappush(maxheap, (-val, i))
            
        return res 


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
  
#     def longestSubarray(self, nums: List[int], limit: int) -> int:sub:
#       n = len(nums)
        
#       max_d = 0
#       for left in range(n):
#         local_max = float('-inf')
#         local_min = float('inf')

#         for right in range(left + 1, n + 1):
#           sub = nums[left:right]
          
#           if local_max < sub[-1]:
#             local_max = sub[-1]
            
#           if local_min > sub[-1]:
#             local_min = sub[-1]
          
#           if local_max - local_min <= limit:
#             if right - left + 1 > max_d:
#               max_d = right - left + 1
#               # print(max_d, right, left, sub)
#           else:
#             break
      
#       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:
                # print(\"pop\", left, right, res, minimum, maximum, )
                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)
            # print(left, right, res, minimum, maximum, )
        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:
        minHeap, maxHeap = [], []
        
        result = i = 0
        
        for j in range(len(nums)):
            heapq.heappush(minHeap, [nums[j], j])
            heapq.heappush(maxHeap, [-nums[j], j])
            
            while -maxHeap[0][0] - minHeap[0][0] > limit:
                i = min(maxHeap[0][1], minHeap[0][1]) + 1
                while minHeap[0][1] < i:
                    heapq.heappop(minHeap)
                while maxHeap[0][1] < i:
                    heapq.heappop(maxHeap)
            
            result = max(result, j - i + 1)
        
        return result

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        max_len = 0
        maxi = nums[0]
        mini = nums[0]
        start = 0
        temp = []
        for i in range(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:
        max_stack = []
        min_stack = []
        l = 0
        ans = 0
        for r in range(len(nums)):
            while max_stack and nums[max_stack[-1]] < nums[r]:
                max_stack.pop()
            max_stack.append(r)
            while min_stack and nums[min_stack[-1]] > nums[r]:
                min_stack.pop()
            min_stack.append(r)
            while max_stack and min_stack and nums[max_stack[0]] - nums[min_stack[0]] > limit:
                if max_stack[0] <= l:
                    max_stack.pop(0)
                if min_stack[0] <= l:
                    min_stack.pop(0)
                l += 1
            ans = max(ans, r - l + 1)
        return ans



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]]) # map value -> count
        while rhs < len(nums):
            # print(f\"lhs: {lhs}, rhs: {rhs}\")
            sd.add(nums[rhs])
            # print(sd)
            if (sd[len(sd)-1] - sd[0] <= limit):
                # print(f\"{sd[len(sd)-1]}-{sd[0]} > {limit}\")
                
                diff_len = max(diff_len, rhs-lhs+1)
                # print(f\"diff_len {diff_len}\")
                
            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:
        
        maxq = []
        minq = []
        left = 0
        res = 0

        for i in range(len(nums)):
            heapq.heappush(maxq, [-nums[i], i])
            heapq.heappush(minq, [nums[i], i])
            
            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)
            
            # print(maxq)
            # print(minq)
            
            res = max(res, i-left+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
        
#         min_heap = [nums[0]]
#         max_heap = [-nums[0]]
        
#         min_removed = {}
#         max_removed = {}
        
#         max_stretch = 1
#         start = 0
#         end = 0
#         while end < len(nums) - 1:
#             end += 1
#             heapq.heappush(min_heap, nums[end])
#             heapq.heappush(max_heap, -nums[end])
            
#             while - max_heap[0] - min_heap[0] > limit:
#                 if nums[start] not in min_removed:
#                     min_removed[nums[start]] = 0
#                 min_removed[nums[start]] += 1
                
#                 if nums[start] not in max_removed:
#                     max_removed[nums[start]] = 0
#                 max_removed[nums[start]] += 1
                
#                 while -max_heap[0] in max_removed and max_removed[-max_heap[0]] > 0:
#                     max_removed[-max_heap[0]] -= 1
#                     heapq.heappop(max_heap)
                    
#                 while min_heap[0] in min_removed and min_removed[min_heap[0]] > 0:
#                     min_removed[min_heap[0]] -= 1
#                     heapq.heappop(min_heap)
                    
#                 start += 1
                
#             if end - start + 1 > max_stretch:
#                 max_stretch = end - start + 1
                
#         return max_stretch


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        answer = 1
        max_val = nums[0]
        min_val = nums[0]
        counts = {nums[0] : 1}
        subarray = deque([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:
                            max_val = max(subarray)
                            break
                        elif min_val == num:
                            min_val = min(subarray)
                            break
                           
            answer = max(answer, len(subarray))
        
        return answer


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:
#         lhs = 0
#         rhs = 1
#         diff_len = 1
#         sd = SortedList([nums[lhs]]) # map value -> count
#         while rhs < len(nums):
#             # print(f\"lhs: {lhs}, rhs: {rhs}\")
#             sd.add(nums[rhs])
#             # print(sd)
#             if (sd[len(sd)-1] - sd[0] <= limit):
#                 # print(f\"{sd[len(sd)-1]}-{sd[0]} > {limit}\")
                
#                 diff_len = max(diff_len, rhs-lhs+1)
#                 # print(f\"diff_len {diff_len}\")
                
#             else:
#                 sd.discard(nums[lhs])
#                 lhs += 1
#             rhs += 1
#         return diff_len
        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()
    
    # append val in constant time 
    def append(self, val, idx):
        while self.queue and self.queue[-1][0] > val:
            self.queue.pop()
        self.queue.append((val, idx))
        #print(\"minQueue is\", self.queue)
        
    def getMin(self, left_idx):
        while self.queue and self.queue[0][1] < left_idx:
            self.queue.popleft()
        #print(\"l is\", left_idx, \"minQ, \",self.queue)
        return self.queue[0][0]
        
class maxQueue(object):
    def __init__(self):
        self.queue = collections.deque()
    
    # append val in constant time 
    def append(self, val, idx):
        while self.queue and self.queue[-1][0] < val:
            self.queue.pop()
        self.queue.append((val, idx))
        #print(\"maxqueue is\", self.queue)
    
        
    def getMax(self, left_idx):
        while self.queue and self.queue[0][1] < left_idx:
            self.queue.popleft()
        #print(\"l is\", left_idx, \"minQ, \" ,self.queue)
        return self.queue[0][0]
    
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # condition is getMax - getMin <= limit
        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: # window meaning: l and r is included in the window
            while r<n and cond:
                #print(\"cond true l, r is\", l, r)
                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:
                #print(\"cond false l, r is\", l, r)
                l += 1
                #print(maxQ.getMax(l), minQ.getMin(l))
                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
                # print(count)
                # print(min_heap)
                # print(ans)
                # print(min_val)
                # print(max_val)
                # Pop min_heap until you have a valid min_val
                if popped_val == min_val and count[popped_val] == 0:
                    while count[min_val] == 0:
                        heapq.heappop(min_heap)
                        min_val = min_heap[0]
                # Pop max_heap until you have a valid max_val
                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):
            # print(max_q.queue, min_q.queue)
            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):
        #[2,5,3,1]  3
        # 1,2,3,5
        # 5,3,2,1
        count = 0
        # get min and max
        #move to the right until the min or max are popped up 
        minValuePos = self.q[0][1]
        maxValuePos = self.qmx[0][1]
        self.start = min (minValuePos,maxValuePos) +1
        
        #update new q
        while self.q[0][1] < self.start:
            heapq.heappop(self.q)
        while self.qmx[0][1] < self.start:
            heapq.heappop(self.qmx)
        
        
        #self.q = []
        #for i in range(self.start, self.end +1):
        #    self.q.append([self.nums[i],i])
        #heapq.heapify(self.q)
        
        
    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()
            #print(self.start, self.end, minValue,maxValue)
            if maxValue - minValue <= limit:
                #print(minValue, maxValue, nums[start:end+1])
                size = max(size, self.end - self.start + 1)
                #extend 
                self.moveEndRight()
            else:
                self.moveStartRight()


        return size
        


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)
            while maxQ[0] - minQ[0] > limit:
                if maxQ[0] == nums[i]: maxQ.popleft()
                elif minQ[0] == nums[i]: minQ.popleft()
                i += 1
            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, 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:
        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 += 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


from sortedcontainers import SortedList
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        if not nums:
            return 0
        
        pq_min = SortedList([])
        pq_max = SortedList([])
        
        st, end, res = 0, 0, 0
        for val in nums:
            pq_min.add(val)
            pq_max.add(-val)
            end+=1
            
            #print(pq_min)
            #print(pq_max)
            #print(\" - \")
            
            while abs(pq_min[0] + pq_max[0]) > limit:
                pq_min.remove(nums[st])
                pq_max.remove(-nums[st])
                st+=1
                
            #print(pq_min)
            #print(pq_max)
            #print(\" ----------- \")
            
            res = max(res, end - st)
        
        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, r = 0, 1
        cur_mx, cur_mi = nums[0], nums[0]
        
        max_l = 1
        
        while l <= r and r < len(nums):
            cur_mx = max(cur_mx, nums[r])
            cur_mi = min(cur_mi, nums[r])
            
            if cur_mx - cur_mi <= limit:
                max_l = max(max_l, r - l + 1)
                r += 1
            else:
                cur_mx = max(nums[l+1: r+1])
                cur_mi = min(nums[l+1: r+1])
                r += 1
                l += 1
        
        return max_l
                


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):
            if (len(minheap)> 0 and minheap[0].val < nums[index] - limit):
                while len(minheap)> 0  and  (minheap[0].val< nums[index] - limit or minheap[0].index < leftIndex):
                    temp = heapq.heappop(minheap) 
                    if (temp.index > leftIndex):
                        leftIndex = temp.index
            if len(maxheap)> 0 and (-maxheap[0].val > nums[index] + limit):    
                while len(maxheap) > 0 and (-maxheap[0].val >  nums[index] + limit or  maxheap[0].index < leftIndex ):
                    temp = heapq.heappop(maxheap)
                    if (temp.index > leftIndex):
                        leftIndex = temp.index 
            heapq.heappush(minheap, Item(nums[index], index))
            heapq.heappush(maxheap, Item(-nums[index], index))
            maxLen = max(maxLen, index - leftIndex)
            index += 1
        return maxLen
                               
                               


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]) # add first element and its index
        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
        
#         minheap=[]
#         maxheap=[]
#         heapq.heapify(minheap)
#         heapq.heapify(maxheap)
#         length=1
#         i=0
#         j=1
#         heapq.heappush(minheap,[nums[0],0]) # add first element and its index
#         heapq.heappush(maxheap,[-nums[0],0])
#         maxindex=0
#         while i<=j and j<=len(nums)-1:
#             if abs(minheap[0][0]-nums[j])<=limit and abs(abs(maxheap[0][0])-nums[j])<= limit:
#                 length=max(length,j-i+1)
                
#             else:
#                 while len(minheap)>0 and abs(minheap[0][0]-nums[j])>limit:
#                     ele,index=heapq.heappop(minheap)
#                     maxindex=max(maxindex,index)
#                 while len(maxheap)>0 and abs(-maxheap[0][0]-nums[j])>limit:
#                     ele,index=heapq.heappop(maxheap)
#                     maxindex=max(maxindex,index)
#                 i=maxindex+1   # update i and now  we are not concerned with element before ith index
#             heapq.heappush(minheap,[nums[j],j]) # add  element and its index
#             heapq.heappush(maxheap,[-nums[j],j])
#             j=j+1
            
#         return length
        
#         def isValid(int_diff, j, max_value, min_value, limit, nums):
#             max_boundary = abs(max_value - nums[j])
#             min_boundary = abs(min_value - nums[j])
#             return int_diff <= limit and max_boundary <= limit and min_boundary <= limit
        
#         def find_error(int_diff,i, j, max_value, min_value, limit, nums,cache):
#             max_boundary = abs(max_value - nums[j])
#             min_boundary = abs(min_value - nums[j])
            
#             if int_diff > limit: return i
#             if max_boundary > limit: return cache[max_value]
#             if min_boundary > limit: return cache[min_value]
            
#         output = 1
#         i = 0
#         idx = 0
#         cache = defaultdict(int)
#         while i < len(nums) and idx < len(nums)-1:
#             min_value = float('inf')
#             max_value = float('-inf')
#             cache[min_value] = i
#             cache[max_value] = i
#             for j in range(i,len(nums)):
                
#                 int_diff = abs(nums[j] - nums[i])
#                 temp_min = min_value
#                 temp_max = max_value
#                 min_value = min(min_value, nums[j])
#                 max_value = max(max_value, nums[j])
#                 if temp_min != min_value:
#                     cache[min_value] = j
#                 if temp_max != min_value:
#                     cache[max_value] = j
#                 if isValid(int_diff, j, max_value, min_value, limit, nums):
#                     output = max(output, (j - i) + 1)
#                 else:
#                     i = find_error(int_diff, i, j, max_value, min_value, limit, nums,cache) + 1
                    
#                     break
#                 idx = j
#         return output
                
                
        
            


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

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        answer = 1
        max_val = nums[0]
        min_val = nums[0]
        counts = {nums[0] : 1}
        subarray = deque([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 True:
                    num = subarray.popleft()
                    counts[num] -= 1 

                    if counts[num] == 0:
                        if max_val == num:
                            max_val = max(subarray)
                            break
                        elif min_val == num:
                            min_val = min(subarray)
                            break
                           
            answer = max(answer, len(subarray))
        
        return answer


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 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]) # add first element and its index
        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
        
#         def isValid(int_diff, j, max_value, min_value, limit, nums):
#             max_boundary = abs(max_value - nums[j])
#             min_boundary = abs(min_value - nums[j])
#             return int_diff <= limit and max_boundary <= limit and min_boundary <= limit
        
#         def find_error(int_diff,i, j, max_value, min_value, limit, nums,cache):
#             max_boundary = abs(max_value - nums[j])
#             min_boundary = abs(min_value - nums[j])
            
#             if int_diff > limit: return i
#             if max_boundary > limit: return cache[max_value]
#             if min_boundary > limit: return cache[min_value]
            
#         output = 1
#         i = 0
#         idx = 0
#         cache = defaultdict(int)
#         while i < len(nums) and idx < len(nums)-1:
#             min_value = float('inf')
#             max_value = float('-inf')
#             cache[min_value] = i
#             cache[max_value] = i
#             for j in range(i,len(nums)):
                
#                 int_diff = abs(nums[j] - nums[i])
#                 temp_min = min_value
#                 temp_max = max_value
#                 min_value = min(min_value, nums[j])
#                 max_value = max(max_value, nums[j])
#                 if temp_min != min_value:
#                     cache[min_value] = j
#                 if temp_max != min_value:
#                     cache[max_value] = j
#                 if isValid(int_diff, j, max_value, min_value, limit, nums):
#                     output = max(output, (j - i) + 1)
#                 else:
#                     i = find_error(int_diff, i, j, max_value, min_value, limit, nums,cache) + 1
                    
#                     break
#                 idx = j
#         return output
                
                
        
            


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:
        if not len(nums): return 0
        
        ml, 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:# we will pop out numbers until max - min < limit
                start += 1

                while pqmax and pqmax[0][1] < start: heapq.heappop(pqmax) ## I only care if the max number index has been passed, if yes, we should pop out all numbers before that
                while pqmin and pqmin[0][1] < start: heapq.heappop(pqmin)## I only care if the min number index has been passed, if yes, we should pop out all numbers before that
            ml = max(ml, end - start + 1)
            
        return ml


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):
            #step 1, check if the min and max has changed?
            #In this step we disgarded the first element, and added the last element
            mini = min(nums[start:end])
            maxi = max(nums[start:end])
            if abs(mini - maxi) > limit:
                start += 1
                end += 1
            else:
                # step2, the current condition is satisfied, explore the next element until
                # the limit is broken
                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() # decreasing 9 5 1
        mini=deque() # increasing 1 5 9
        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:
                # remove elements outside of the window
                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


from collections import deque
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        asc = deque()
        dsc = deque()
        ret=l=0
        for i in range(len(nums)):
            n=nums[i]
            while asc and n<asc[-1]:
                asc.pop()
            asc.append(n)
            while dsc and n>dsc[-1]:
                dsc.pop()
            dsc.append(n)
            while dsc[0]-asc[0]>limit:
                if dsc[0]==nums[l]:
                    dsc.popleft()
                if asc[0]==nums[l]:
                    asc.popleft()
                l+=1
            ret = max(ret,i-l+1)
        return ret

class Solution:
  # 520 ms
  def longestSubarray(self, nums, limit):
    # initialize maximum and minimum
    _min = _max = nums[0]
    count = 0
    res, start =1, 0

    for right in range(len(nums)):
      # update maximum and minimum
      if _min > nums[right]: _min = nums[right]
      if _max < nums[right]: _max = nums[right]

      # if the right bound valid, count and update result 
      if _max - _min <= limit:
        count += 1
        if res < count: res = count

      # if invalid, turn to find the valid left bound
      elif _max - _min > limit:
        # initialize maximum and minimum at this position
        _min = _max = nums[right]
        count = 1
        left = right - 1
        # keep updating until invalid
        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
        # when ended, update the left bound to right+1
        # because we have counted the \"right\" position now in while-loop above already
        start = right + 1

    return res

from collections import deque
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        asc = deque()
        dsc = deque()
        ret=l=0
        for i in range(len(nums)):
            n=nums[i]
            while asc and n<asc[-1]:
                asc.pop()
            asc.append(n)
            while dsc and n>dsc[-1]:
                dsc.pop()
            dsc.append(n)
            while dsc[0]-asc[0]>limit:
                if nums[l]==dsc[0]:
                    dsc.popleft()
                if nums[l]==asc[0]:
                    asc.popleft()
                l+=1
            ret = max(ret,i-l+1)
        return ret

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:
        from collections import deque
        
        min_q = deque()
        max_q = deque()
        ans = 0
        j = 0
        for i, num in enumerate(nums):
            while min_q and min_q[-1][0] > num:
                min_q.pop()
            min_q.append((num, i))
            while max_q and max_q[-1][0] < num:
                max_q.pop()
            max_q.append((num, i))
            if abs(min_q[0][0] - max_q[0][0]) <= limit:
                ans = max(ans, i - j + 1)
            else:
                if min_q[0][1] < max_q[0][1]:
                    j = min_q[0][1] + 1
                    min_q.popleft()
                elif min_q[0][1] > max_q[0][1]:
                    j = max_q[0][1] + 1
                    max_q.popleft()
                else:
                    j = max_q[0][1] + 1
                    min_q.popleft()
                    max_q.popleft()
            # print(ans, min_q, max_q, j)
        return ans

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)
            # print(ans, l, r, incStack, decStack)
        return ans

import collections
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # sliding window
        mx, mn = collections.deque([0]), collections.deque([0])
        ans = 1
        left = 0
        for i in range(1, len(nums)):
            # update max and min monotonic q
            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
    
            
        
        
        
        
        
        
#         res = 0
#         maxq = []
#         minq = []
#         j = 0
#         for i,n in enumerate(nums): # O(n)
#             heapq.heappush(maxq, [-n,i] )  # O(log n)
#             heapq.heappush(minq, [n,i] )
            
#             while -maxq[0][0] - minq[0][0] > limit:
#                 ind = min( maxq[0][1], minq[0][1] )
#                 while maxq[0][1] <= ind:
#                     heapq.heappop(maxq) # O(log n)
#                 while minq[0][1] <= ind:
#                     heapq.heappop(minq)
#                 j = ind+1
#             res = max(res, i - j +1 )
            
#         return res
                
        
        
        
        
        
#         res = 0
        
#         i = 0
#         arr = [] # space O(res)
#         for n in nums:  # O(n) time
#             bisect.insort(arr, n) # O(res)
#             while arr[-1] - arr[0] > limit:
#                 ind = bisect.bisect_right(arr, nums[i])  # O( log res )
#                 arr.pop(ind-1)  # O(res)
#                 i += 1
#             res = max(res, len(arr))
            
#         return res
                
        
        
        
        
        


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:
        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)
            
            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
                l += 1
                if l > min_deque[0]:
                    min_deque.popleft()
                if l > max_deque[0]:
                    max_deque.popleft()
            
            ans = max(ans, r - l + 1)
            r += 1
                
        return ans

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


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, 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:
        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)
            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
                l += 1
                if l > min_deque[0]:
                    min_deque.popleft()
                if l > max_deque[0]:
                    max_deque.popleft()
            ans = max(ans, r-l + 1)
            r += 1
        return ans
 



        
        
        


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:
        maxd = collections.deque() # monotonically decreasing 
        mind = collections.deque() # monotonically increasing 
        i = 0
        # maxd[-1] gives last element and maxd[0] gives first/front element
        
        for num in nums:
            while maxd and num > maxd[-1]: maxd.pop() # biggr num eats up all smaller ones
            while mind and num < mind[-1]: mind.pop()
            maxd.append(num)
            mind.append(num)
            if maxd[0] - mind[0] > limit:
                if maxd[0] == nums[i]: maxd.popleft()
                if mind[0] == nums[i]: mind.popleft()
                i+=1
        return len(nums) -i
                
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # read - https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609708/Python-Clean-Monotonic-Queue-solution-with-detail-explanation-O(N)


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:
                while min_deque[0] <= l:
                    min_deque.popleft()
                while max_deque[0] <= l:
                    max_deque.popleft()
                l += 1
            ans = max(ans, r - l + 1)
            r += 1
                
        return ans

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        
        # nums = [8,2,4,7]
        # max_len = 0
        # first = 0
        # second = 0
        
        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:
        # keep track of max and min value of sliding window
        # mono decreasing deque
        max_deque = collections.deque()
        # mono increasing 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)
            # if current window violate the limit,
            # then it is guarantee current num change either 
            # head of max_deque or min_deque
            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)
        
            


from collections import deque

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        if not nums:
            return 0
        
        minq, maxq = deque(), deque()
        l = r = 0
        ans = 0
        while r < len(nums):
            while minq and nums[r] <= nums[minq[-1]]:
                minq.pop()
            while maxq and nums[r] >= nums[maxq[-1]]:
                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:
        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:
        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 )
            # print(i,nums[i], inc,dec, start_pos, ans)
            
        return ans
            


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        i,j=0,0
        nums.append(float('inf'))
        qmin=collections.deque() # monotonic non-decreasing
        qmax=collections.deque() # non-increasing 
        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)
                
                
            # only one can happen
            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

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        i,j=0,0
        nums.append(float('inf'))
        qmin=collections.deque() # monotonic non-decreasing
        qmax=collections.deque() # non-increasing 
        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)
                
                
            # only one can happen
            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, 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        

from collections import deque
class Solution:
    def longestSubarray(self, nums, limit):
        mini, maxi, res, j  = deque([]), deque([]), 0, 0

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

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:
        '''
        # Complexity of n^2
        i = 0
        j = 0
        
        maxSize = 0
        while j < len(nums):
            k = j - 1 # 1
            while k >= i:
                if abs(nums[k] - nums[j]) > limit:
                    i = k + 1 
                    
                k -= 1
                 
            maxSize = max(maxSize, (j-i+1))
            j += 1
            
        return maxSize
        
        '''
        
        sP = 0
        eP = 0
        minQ = collections.deque([])
        maxQ = collections.deque([])
        maxSize = 0
        
        # maxS = 3
        # ep  - 4
        # sp  - 2
        
        #  0 1 2 3 4 5
        # 10 1 2 1 7 2
        # minQ (3,1)
        # maxQ (4,7)
        
    
        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 # this is the new i to start
                while minVals[0][1] < i:
                    heappop(minVals)
                
                while maxVals[0][1] < i:
                    heappop(maxVals)
                
            #print(nums[i:j+1], bestSize)
            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

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)
            
            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
                if l == min_deque[0]:
                    min_deque.popleft()
                if l == max_deque[0]:
                    max_deque.popleft()
                l += 1
            ans = max(ans, r - l + 1)
            r += 1
                
        return ans

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)
            
            # print(\"1\", max_q, min_q)
            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(\"2\", max_q, min_q)
            
            print((end - start + 1))
            res = max(res, end - start + 1)
            end += 1
        
        return res
            


from collections import deque
class Solution: #revisit 09/09/2020
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # for a window, find the window max and the window min
        # left and right pointer
        # use max_queue and min_queue to calculate the window max and window min
        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
                
# e.g. [10,1,2,4,7,2], limit = 5
# left, right =2,5, min_q = [(5,2)], max_q = [(4,7), (5,2)] max_lenght = 4











# from collections import deque
# class Solution:
#     def longestSubarray(self, nums: List[int], limit: int) -> int:
#         N = len(nums)
#         if N == 1:
#             return 1
        
#         result = 0
#         min_q, max_q = deque([]), deque([])
#         l, r = 0, 0
#         while r < N:
#             while min_q and nums[min_q[-1]] >= nums[r]:
#                 min_q.pop()
#             while max_q and nums[max_q[-1]] <= nums[r]:
#                 max_q.pop()
#             min_q.append(r)
#             max_q.append(r)
            
#             while nums[max_q[0]] - nums[min_q[0]] > limit:
#                 l += 1
#                 if max_q[0] < l:
#                     max_q.popleft()
#                 if min_q[0] < l:
#                     min_q.popleft()
                    
#             #print(f\"l = {l}, r = {r}, min_q = {min_q}, max_q = {max_q}\")
#             result = max(result, r - l + 1) 
#             r += 1
#         return result
        


class Solution:

    def longestSubarray(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        max_q = deque() #3,2,1,0
        min_q = deque() #1,2,3,4

        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:
        #[10,1,2,4,7,2]
        #queue = [4, 7, 2, 8]
        #min_queue = [2, 8]
        #max_queue = [8]
        #limit: 5
        #ans: 4
        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:
        #[10,1,2,4,7,2]
        #queue = [4, 7, 2, 8]
        #min_queue = [2, 8]
        #max_queue = [8]
        #limit: 5
        #ans: 4

        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


# 注意需要标记滑动窗口内min和max的取值， 否则有可能超时
# 这题需要使用单调栈或者最小最大堆


import heapq as hq

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:
        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:
                # print(ld, sd, \"  ------\")
                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
                # print(ld, sd)
                # start = min(ld[0][1], sd[0][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() #(index, value)
        
        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:
        ans = 0
        min_deque, max_deque = collections.deque(), collections.deque()
        l = r = 0
        
        while r < len(nums):
            while min_deque and nums[min_deque[-1]] >= nums[r]:
                min_deque.pop()
            while max_deque and nums[max_deque[-1]] <= nums[r]:
                max_deque.pop()
            min_deque.append(r)
            max_deque.append(r)
            
            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
                l += 1
                if max_deque[0] < l:
                    max_deque.popleft()
                if min_deque[0] < l:
                    min_deque.popleft()
            
            ans = max(ans, r-l+1)
            r += 1
            
        return ans

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:
        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()
                elif left == min_q[0]:
                    min_q.popleft()
                    
                left += 1
            
            result = max(result, i - left + 1)
        return result

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)):
            n = nums[i]
            while minq and n<minq[-1]:
                minq.pop()
            minq.append(n)
            while maxq and n>maxq[-1]:
                maxq.pop()
            maxq.append(n)
            while maxq[0]-minq[0]>limit:
                if minq[0]==nums[l]:
                    minq.popleft()
                if maxq[0]==nums[l]:
                    maxq.popleft()
                l+=1
            ret = max(ret,i-l+1)
        return ret

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):
            # print(i, j, max_len)
                    
            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
            # print(i, j, max_len)
            # print('-------------')
        return max_len

#make every num in nums become right bound for the subarray once, and find the longest subarray.
#i need to know the max and min value in the subarray, so I'll maintain a  minHeap, maxHeap with (value, index), then I can alway cost O(logn) to get the max and min value.
#O(NlogN)
#
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        VALUE, INDEX = 0, 1
        left = 0
        min_h, max_h = [], []
        max_len = 0
        #nums = [8,2,4,7]
        for right, num in enumerate(nums): #right= 3, left = 2
            heappush(min_h, (num, right)) #max = [(-7,3)(-4,2)(-2,1)]
            heappush(max_h, (-num, right)) #min = [(4,2)(7,3) (8,0)]
            #check whether the current subarray is valid
            #if it is invalid, pop out the extreme value
            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
                #clean heap
                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) #max_len = 2
        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