<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:
        #数组长度为奇数 
    #距离和 = a[n-1] + a[n-2] + .. + a[n/2 + 1] - (a[0]+ a[1]+ ... + a[n/2-1])
    #偶数 -- a[n-1] + a[n-2] + .. + a[n/2] - (a[0]+ a[1]+ ... + a[n/2-1])
    #随着窗口向右 每个数字依次经历 正(被加) -- 正中间 -- 负(被减)
    #随着right 指针的元素 进来 + right ， 那什么被减呢或者原来有影响的有没有可能没有影响了
    # [10 20] -- 20 -10 ----> [10 20 30] -- 30 - 10, 20 没影响了 -- delta = 30 - 20 - 进来的 - 中位
    # [10 20 30 40] -- 40 - 20 + 30 - 20 + 20 - 10 ---> 40 + 30 - 20 -10 --- 20变成负的了 -- delta = 40 - 20 -- 进来的 - 中位数
    #进来一个数字 delta 是 --  a(i) - a(i/2)
        nums.sort()
        ans = left = 0
        s = 0 #到mid距离
        for right, x in enumerate(nums):
            s += x - nums[(left+right)//2]
            while s > k:
     #左指针怎么移动呢！
    #左边数移除可能中间变化有问题的 -- 和上面一样的考虑
    # [10 20 30 40] -- 40 - 20 + 30 - 20 + 20 - 10 = 40 + 30 - 20 - 10 -- a3 + a2 - a1 - a0
    #10 [20 30 40] -- 40 - 30 + 30 - 20 -- 40 - 20 -- a3 - a1 --- delta = a0 - a2 -- 新-旧
    # 都是根据原list而言 --- a0 我移出去的数字， a2 mid右侧的数字
                s += nums[left] - nums[(left+right+1)//2]
            #(left+right+1)//2向上取整 -- 偶数时候 但是你不能改变奇数时候就是mid的事实！！！
                left += 1
            ans = max(ans, right - left + 1)
        return ans
712