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

<p>You can perform the following operation on the array <strong>at most</strong> <code>k</code> times:</p>

<ul>
	<li>Choose any index <code>i</code> from the array and <strong>increase</strong> or <strong>decrease</strong> <code>nums[i]</code> by <code>1</code>.</li>
</ul>

<p>The score of the final array is the <strong>frequency</strong> of the most frequent element in the array.</p>

<p>Return <em>the <strong>maximum</strong> score you can achieve</em>.</p>

<p>The frequency of an element is the number of occurences of that element in the array.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,6,4], k = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can do the following operations on the array:
- Choose i = 0, and increase the value of nums[0] by 1. The resulting array is [2,2,6,4].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,3].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,2].
The element 2 is the most frequent in the final array so our score is 3.
It can be shown that we cannot achieve a better score.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,4,4,2,4], k = 0
<strong>Output:</strong> 3
<strong>Explanation:</strong> We cannot apply any operations so our score will be the frequency of the most frequent element in the original array, which is 3.
</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;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= k &lt;= 10<sup>14</sup></code></li>
</ul>

# class Solution:
#     def maxFrequencyScore(self, nums: List[int], k: int) -> int:
#         nums.sort()
#         print(nums)
#         d, n = {}, len(nums)
#         for i in nums:
#             d[i] = d.get(i, 0) + 1
        
#         l = [[i, j] for i, j in d.items()]
#         maxi = 1
        
#         for i, freq in l:
#             low, high = bisect_left(nums, i), bisect_right(nums, i) - 1
#             l, r = low - 1, high + 1
    
#             cnt = freq  
            
#             remaining_k = k
            
#             while l >= 0 and r < n and remaining_k:
#                 if abs(nums[low] - nums[l]) <= abs(nums[r] - nums[high]):
#                     if remaining_k >= nums[low] - nums[l]:
#                         cnt += 1
#                         remaining_k -= nums[low] - nums[l]
#                         l -= 1
#                     else:
#                         break
#                 else:
#                     if remaining_k >= nums[r] - nums[high]:
#                         cnt += 1
#                         remaining_k -= nums[r] - nums[high]
#                         r += 1
#                     else:
#                         break
            
#             while l >= 0 and remaining_k:
#                 if remaining_k >= nums[low] - nums[l]:
#                     cnt += 1
#                     remaining_k -= nums[low] - nums[l]
#                     l -= 1
#                 else:
#                     break
            
#             while r < n and remaining_k:
#                 if remaining_k >= nums[r] - nums[high]:
#                     cnt += 1
#                     remaining_k -= nums[r] - nums[high]
#                     r += 1
#                 else:
#                     break
#             if i==101:
#                 print(cnt)
#             maxi = max(cnt, maxi)
        
#         return maxi



class Solution:
    def IsPossible(self, length: int, arr: List[int], k: int) -> bool:
        n = len(arr)
        if length > n:
            return False
        
        prefix = [0] * n
        prefix[0] = arr[0]
        for i in range(1, n):
            prefix[i] = arr[i] + prefix[i - 1]
        
        for i in range(n - length + 1):
            l, r = i, i + length - 1
            med = (l + r) // 2
            
            less = (med - l + 1) * arr[med] - (prefix[med] - (prefix[l - 1] if l - 1 >= 0 else 0))
            more = 0 if r <= med else (prefix[r] - prefix[med]) - (r - med) * arr[med]
            
            if less + more <= k:
                return True
        
        return False

    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = 1
        n = len(nums)
        low, high = 1, n  
        
        while low <= high:
            mid = (low + high) // 2
            if self.IsPossible(mid, nums, k):
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
        
        return ans

1427