<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>

from typing import List

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:

        a = sorted(nums)

        left = 0
        right = 0

        ans = 1

        used = 0
        for i in range(len(a)):
            if i>0:
                # as we move forward, we need to remove the decrements in front of us
                if right>=i:
                    used-=(a[i]-a[i-1]) * (right-i+1)

                if left ==i-1:
                    left = i
                else:

                    # and we also need to add to increment those behid us, so they can keep up
                    used+=(a[i]-a[i-1])*(i-left)

            while used>k and (right>i or left<i):
                if a[right]-a[i] >= a[i]-a[left]:
                    used-=a[right]-a[i]
                    right-=1
                else:
                    used-=a[i]-a[left]
                    left+=1
            if left>i:
                left = i
            if right<i:
                right = i

            can_continue = True
            while can_continue:
                can_continue = False

                another = True
                while another:
                    another = False
                    if left < i and right + 1 < len(a) and a[right + 1] - a[i] < a[i] - a[left]:
                        used -= a[i] - a[left]
                        left += 1
                        right += 1
                        used += a[right ] - a[i]
                        another = True
                        continue

                    if right > i and left - 1 >= 0 and a[i] - a[left - 1] < a[right] - a[i]:
                        used -= a[right] - a[i]
                        right -= 1
                        left -= 1
                        used += a[i] - a[left]
                        another = True
                        continue

                if left-1>=0 and a[i]-a[left-1] <=k-used:
                    can_continue = True
                if right+1<len(a) and a[right+1]-a[i]<=k-used:
                    can_continue = True
                if not can_continue:
                    break

                if left-1>=0 and right+1<len(a):
                    if a[i]-a[left-1] >= a[right+1]-a[i]:
                        right+=1
                        used+=a[right]-a[i]
                    else:
                        left-=1
                        used+=a[i]-a[left]

                elif left-1>=0:
                    left -= 1
                    used += a[i] - a[left]
                else:
                    right += 1
                    used += a[right] - a[i]


            ans = max(ans,right-left+1)
            #print(right-left+1,a[i])

        # for i in range(0,max(a)+1):
        #     b = []
        #     for j in a:
        #         b.append(abs(j-i))
        #     b = sorted(b)
        #     count = 0
        #     j = 0
        #     naj =  -1
        #     while b[j]+count<=k:
        #         naj = j+1
        #         count+=b[j]
        #         j+=1
        #     print(naj,i)
        return ans

# print(Solution.maxFrequencyScore(None, nums = [16,2,6,20,2,18,16,8,15,19,22,29,24,2,26,19], k = 40)) # 11
# 
# 
# print(Solution.maxFrequencyScore(None, nums=[27, 8, 30, 3, 13, 28, 7, 14, 21, 19, 24, 28, 29, 1, 14, 22, 6],
#                                      k=23))  # 8
# 
# 
# print(Solution.maxFrequencyScore(None, nums = [3,20,13,2,3,15,24,19,8,13,19,20,21], k = 45)) # 10
# 
# print(Solution.maxFrequencyScore(None, nums = [1,2,6,4], k = 3)) # 3
# print(Solution.maxFrequencyScore(None, nums = [1,4,4,2,4], k = 0)) # 3

1147