<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> and an integer <code>k</code>.</p>

<p>A subarray is called <strong>equal</strong> if all of its elements are equal. Note that the empty subarray is an <strong>equal</strong> subarray.</p>

<p>Return <em>the length of the <strong>longest</strong> possible equal subarray after deleting <strong>at most</strong> </em><code>k</code><em> elements from </em><code>nums</code>.</p>

<p>A <b>subarray</b> is a contiguous, possibly empty sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,2,3,1,3], k = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> It&#39;s optimal to delete the elements at index 2 and index 4.
After deleting them, nums becomes equal to [1, 3, 3, 3].
The longest equal subarray starts at i = 1 and ends at j = 3 with length equal to 3.
It can be proven that no longer equal subarrays can be created.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,2,2,1,1], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> It&#39;s optimal to delete the elements at index 2 and index 3.
After deleting them, nums becomes equal to [1, 1, 1, 1].
The array itself is an equal subarray, so the answer is 4.
It can be proven that no longer equal subarrays can be created.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>
	<li><code>0 &lt;= k &lt;= nums.length</code></li>
</ul>

class Heap:

    def __init__(self, capacity = 8):
        self.capacity = capacity
        self.arr = [None for _ in range(self.capacity)]
        self.size = 0

    def __str__(self):
        ans = [str(node) for node in self.arr]
        return " ".join(ans)

    def doubleTheCapacity(self):
        self.arr += [None  for _ in range(self.capacity)]
        self.capacity *= 2

    def add(self, node): 
        if(self.capacity == self.size): self.doubleTheCapacity()
        
        self.arr[self.size] = node
        node.index = self.size
        self.size += 1

        self.heapifyUp(self.size-1)
    
    def peek(self):
        if(self.size == 0): raise Exception("index out of bound")
        return self.arr[0]
    
    def pop(self): 
        if(self.size == 0): raise Exception("index out of bound")

        self.arr[0], self.arr[self.size-1] = self.arr[self.size-1], self.arr[0]
        self.arr[0].index = 0
        self.arr[self.size-1].index = self.size-1
        self.size -= 1
        self.heapifyDown(0)
        return self.arr[self.size]
    
    def increaseKey(self, index, newVal):
        if(index < 0 and index >= self.size): raise Exception("index out of bound")

        self.arr[index].val = newVal
        self.heapifyUp(index)
    
    def decreaseKey(self, index, newVal):
        if(index < 0 and index >= self.size): raise Exception("index out of bound")

        self.arr[index].val = newVal
        self.heapifyDown(index)

    def heapifyUp(self, index): 
        if(index >= self.size): raise Exception("index out of bound")

        while(Heap.hasParent(index) and self.arr[Heap.getParentIndex(index)] < self.arr[index]):
            parentIndex = Heap.getParentIndex(index)
            self.arr[index], self.arr[parentIndex] = self.arr[parentIndex], self.arr[index]
            self.arr[index].index = index
            self.arr[parentIndex].index = parentIndex
            index = parentIndex

    def heapifyDown(self, index): 
        if(self.size == 0): return
        if(index < 0 or index >= self.size): raise Exception("index out of bound")

        greatestIndex = index
        while True:
            leftIndex = Heap.getLeftChildIndex(index)
            rightIndex = Heap.getRightChildIndex(index)
            if(leftIndex < self.size and self.arr[greatestIndex] < self.arr[leftIndex]): greatestIndex = leftIndex
            if(rightIndex < self.size and self.arr[greatestIndex] < self.arr[rightIndex]): greatestIndex = rightIndex

            if(greatestIndex == index): return
            self.arr[index], self.arr[greatestIndex] = self.arr[greatestIndex], self.arr[index]
            self.arr[index].index = index
            self.arr[greatestIndex].index = greatestIndex
            index = greatestIndex

            

    @staticmethod
    def hasParent(index): return index != 0

    @staticmethod
    def getParentIndex(index): return (index-1)//2
    
    @staticmethod
    def getLeftChildIndex(index): return 2*index +1
    
    @staticmethod
    def getRightChildIndex(index): return 2*index +2


class HeapNode:
    def __init__(self, val):
        self.val = val
        self.index = None
    
    def __eq__(self, value):
        return self.val == value.val
    
    def __lt__(self, value):
        return self.val < value.val

    def __str__(self):
        return f'val: {self.val} index: {self.index}'

class Solution:
    
    def longestEqualSubarray(self, nums, K):
        # [)
        
        ans = -10 ** 10
        N = len(nums)
        start = 0
        end = 0
        k = 0
        nodeMap = {}
        heap = Heap()

        while(end < N):
            while(end < N and k <= K):
                if(nums[end] not in nodeMap): 
                    nodeMap[nums[end]] = HeapNode(0)
                    heap.add(nodeMap[nums[end]])
                
                node = nodeMap[nums[end]]
                heap.increaseKey(node.index, node.val +1)
                end += 1

                l = end - start
                maxFreq = heap.peek().val
                k = l - maxFreq
                
                if(k <= K): ans = max(ans, maxFreq)
            

            while(k > K and start < end):
                node = nodeMap[nums[start]]
                heap.decreaseKey(node.index, node.val-1)
                start += 1
                k = (end - start) - heap.peek().val
            
            
            if(heap.size > 0): ans = max(ans, heap.peek().val)
        
        return ans
35200