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

"""
[1,2,6,4]
3
[1,4,4,2,4]
0
[27,8,30,3,13,28,7,14,21,19,24,28,29,1,14,22,6]
23
[1,3,2,324,3,2,1,22,2,11,112,213,212,221,123,321,12,12,4,5,6,78,24,57,46,121]
50
"""
class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        # 1. for a particular windown len, optimal is always to median!!! [(l + r) // 2]th sorted element
        # 2. cost in any windown can be calculated directly w/ prefix sum
        #    [l ... m ... r]
        #    right: (v[r] - v[m]) + (v[r - 1] - v[m]) + ... + (v[m + 1] - v[m]) + (v[m] - v[m])
        #        => (pf[r] - pf[m - 1]) - (v[m] * (r - l + 1))
        #    left: (v[m] - v[l]) + (v[m] - v[l + 1]) + ... (v[m] - v[m])
        #        => (v[m] * (m - l + 1)) - (v[l] * (m - l + 1))
        # 3. simple binary search of win len, each search use a sliding window to find whether len is okay
        def check(mid):
            l = 0
            r = mid - 1
            while r < n:
                m = (l + r) // 2
                # s = (pf[r] - pf[m - 1] - (r - m + 1) * nums[m]) + \
                #     ((m - l + 1) * nums[m] - pf[m] + pf[l - 1] )
                if pf[r] + pf[l - 1] - pf[m] * 2 + (m - l + 1 - r + m) * nums[m] <= k:
                    return True
                r += 1
                l += 1
            return False

        nums.sort()
        items = sorted(Counter(nums).items())
        lo = max(items, key = lambda x: x[1])[1]
        ri = n = len(nums)
        pf = list(accumulate(nums)) + [0]

        while lo < ri:
            mid = (lo + ri + 1) // 2
            if check(mid):
                lo = mid
            else:
                ri = mid - 1
        return lo
1179