<p>The <strong>frequency</strong> of an element is the number of times it occurs in an array.</p>

<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. In one operation, you can choose an index of <code>nums</code> and increment the element at that index by <code>1</code>.</p>

<p>Return <em>the <strong>maximum possible frequency</strong> of an element after performing <strong>at most</strong> </em><code>k</code><em> operations</em>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,4], k = 5
<strong>Output:</strong> 3<strong>
Explanation:</strong> Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.</pre>

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

<pre>
<strong>Input:</strong> nums = [1,4,8,13], k = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,9,6], k = 2
<strong>Output:</strong> 1
</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>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
    void merge(vector<int> &nums,int low,int mid,int high){
        int i=low,j=mid+1;
        // cout<<high<<low;
        int temp[high-low+1];
        int k=0;
        while(i<=mid && j<=high){
            if(nums[i]<nums[j])temp[k++]=nums[i++];
            else temp[k++]=nums[j++];
        }
        while(i<=mid)temp[k++]=nums[i++];
        while(j<=high)temp[k++]=nums[j++];
        k=0;
        for(i=low;i<=high;i++)nums[i]=temp[k++];
    }
    void mergeSort(vector<int>& nums,int low,int high){
        if(low>=high)return;
        int mid = (low+high)/2;
        mergeSort(nums,low,mid);
        mergeSort(nums,mid+1,high);
        merge(nums,low,mid,high);
    }
    void debug(vector<int>& nums){
        for(int i:nums)cout<<i<<" ";
        cout<<"\n";
    }
public:
    int maxFrequency(vector<int>& nums, int k) {
        long n = nums.size();
        mergeSort(nums,0,n-1);
        long l=0;
        long maxWindow=0;
        long total =0;
        for(long r=0;r<n;r++){
            total+=nums[r];
            if(nums[r]*(r-l+1)>total+k){
                total-=nums[l++];
            }
            maxWindow= max(maxWindow,(r-l+1));
        }
        return maxWindow;
    }
};
105000