За один ход увеличить или уменьшить любой элемент массива на 1, всего таких операций можно сделать не больше K

void Main()
{
    var path = @"c:\data\in.txt";
    var lines = File.ReadAllLines(path);
    var k = lines[0].Split(' ').Select(x => int.Parse(x)).Skip(1).First();
    var arr = lines[1].Split(' ').Select(x => int.Parse(x)).ToArray();
 
    var sw = new Stopwatch();
    sw.Start();
    var res = Solve(arr, k);
    sw.Stop();
    Console.WriteLine($"Result = {res}");
    Console.WriteLine($"Time = {sw.ElapsedMilliseconds} ms");
}
 
public int Solve(int[] numbers, int k)
{
    var maxWidth = 1;
    var w = new Treap(numbers[0], 0);
    (int Low, int High) medians = (numbers[0], numbers[0]);
    var stepCount = 0;
 
    for (int i = 1, j = 0; i < numbers.Length;)
    {
        if (stepCount > k)
        {
            var n = numbers[j++];
            Treap.Remove(ref w, n);
            Contraction(n);
            continue;
        }
 
        if (w.Width > maxWidth)
        {
            maxWidth = w.Width;
        }
 
        {
            var n = numbers[i++];
            Treap.Add(ref w, n, i);
            Expansion(n);
        }
    }
    return maxWidth;
 
    void Contraction(int n)
    {
        if (w.Width % 2 == 1)
        {
            if (n >= medians.High)
            {
                medians = (medians.Low, medians.Low);
                stepCount -= n - medians.Low;
            }
            else if (n <= medians.Low)
            {
                medians = (medians.High, medians.High);
                stepCount -= medians.High - n;
            }
            else
            {
                throw new InvalidProgramException("not possible");
            }
        }
        else
        {
            var mOld = medians.High; // w.Medians.High == w.Medians.Low
            if (n > mOld)
            {
                var low = w.OrdinalStat(w.Width / 2 - 1);
                medians = (low, mOld);
                stepCount += mOld - n;
            }
            else if (n < mOld)
            {
                var high = w.OrdinalStat(w.Width / 2);
                medians = (mOld, high);
                stepCount += n - mOld;
            }
            else
            {
                var low = w.OrdinalStat(w.Width / 2 - 1);
                var high = w.OrdinalStat(w.Width / 2);
                medians = (low, high);
                //w.StepCount = w.StepCount;
            }
        }
    }
 
    void Expansion(int n)
    {
        if (w.Width % 2 == 1)
        {
            if (n >= medians.High)
            {
                medians = (medians.High, medians.High);
                stepCount = stepCount + (n - medians.High);
            }
            else if (n <= medians.Low)
            {
                medians = (medians.Low, medians.Low);
                stepCount = stepCount + (medians.Low - n);
            }
            else
            {
                medians = (n, n);
                //w.StepCount = w.StepCount;
            }
        }
        else
        {
            var mOld = medians.High; // w.Medians.High == w.Medians.Low
            if (n > mOld)
            {
                var high = w.OrdinalStat(w.Width / 2);
                medians = (mOld, high);
                stepCount = stepCount + (n - mOld);
            }
            else if (n < mOld)
            {
                var low = w.OrdinalStat(w.Width / 2 - 1);
                medians = (low, mOld);
                stepCount = stepCount + (mOld - n);
            }
            else
            {
                medians = (n, n);
                //w.StepCount = w.StepCount;
            }
 
        }
    }
 
}
 
public class Treap
{
    private int Key;
    private int Prior;
    private int Size;
    
    private Treap Left;
    private Treap Right;
    
    public Treap(int key, int prior, Treap left = null, Treap right = null)
    {
        Key = key;
        Prior = prior;
        Left = left;
        Right = right;
        UpdateSize();
    }
    
    public int Width => Size;
    
    private void UpdateSize()
    {
        Size = (Left?.Size ?? 0) + (Right?.Size ?? 0) + 1;
    }
    
    private static void Split(Treap t, int key, ref Treap l, ref Treap r)
    {
        if (t == null)
        {
            l = r = null;
            return;
        }
        else if (t.Key <= key)
        {
            Split(t.Right, key, ref t.Right, ref r);
            l = t;
        }
        else
        {
            Split(t.Left, key, ref l, ref t.Left);
            r = t;
        }
        t.UpdateSize();
    }
    
    private static void Merge(ref Treap t, Treap l, Treap r)
    {
        if (l == null || r == null)
        {
            t = l ?? r;
        }
        else if (l.Prior > r.Prior)
        {
            Merge(ref l.Right, l.Right, r);
            t = l;
        }
        else
        {
            Merge(ref r.Left, l, r.Left);
            t = r;
        }
        t?.UpdateSize();
    }
    
    public static void Add(ref Treap t, int key, int prior)
    {
        var it = new Treap(key, prior);
        if (t == null)
        {
            t = it;
            return;
        }
        else if (t.Prior < it.Prior)
        {
            Split(t, it.Key, ref it.Left, ref it.Right);
            t = it;
        }
        else if (it.Key < t.Key)
        {
            Add(ref t.Left, key, prior);
        }
        else
        {
            Add(ref t.Right, key, prior);
        }
        t.UpdateSize();
    }
 
    public static void Remove(ref Treap t, int key)
    {
        if (t.Key == key)
        {
            Merge(ref t, t.Left, t.Right);
            return;
        }
        else if (key < t.Key)
        {
            Remove(ref t.Left, key);
        }
        else
        {
            Remove(ref t.Right, key);
        }
        t.UpdateSize();
    }
    
    public int OrdinalStat(int k)
    {
        var curr = this;
        while(curr != null)
        {
            var sizeLeft = curr.Left?.Size ?? 0;
            if (sizeLeft == k) return curr.Key;
            if (sizeLeft < k)
            {
                curr = curr.Right;
                k -= sizeLeft + 1;
            }
            else
            {
                curr = curr.Left;
            }
        }
        throw new IndexOutOfRangeException();       
    }
 
    public override string ToString()
    {
        return $"Key={Key}, Size={Size}, Prior={Prior}";
    }
 
}

public int Solve(int[] numbers, int k)
{
    var maxWidth = 1;
    var w = new SortedSet<(int,int)>();
    w.Add((numbers[0], 0));
    (int Low, int High) medians = (numbers[0], numbers[0]);
    var stepCount = 0;
 
    for (int i = 1, j = 0; i < numbers.Length;)
    {
        if (stepCount > k)
        {
            var n = numbers[j];
            w.Remove((n,j++));
            Contraction(n);
            continue;
        }
 
        if (w.Count > maxWidth)
        {
            maxWidth = w.Count;
        }
 
        {
            var n = numbers[i];
            w.Add((n, i++));
            Expansion(n);
        }
    }
    return maxWidth;
 
    void Contraction(int n)
    {
        if (w.Count % 2 == 1)
        {
            if (n >= medians.High)
            {
                medians = (medians.Low, medians.Low);
                stepCount -= n - medians.Low;
            }
            else if (n <= medians.Low)
            {
                medians = (medians.High, medians.High);
                stepCount -= medians.High - n;
            }
            else
            {
                throw new InvalidProgramException("not possible");
            }
        }
        else
        {
            var mOld = medians.High; // w.Medians.High == w.Medians.Low
            if (n > mOld)
            {
                var low = w.ElementAt(w.Count / 2 - 1).Item1;
                medians = (low, mOld);
                stepCount += mOld - n;
            }
            else if (n < mOld)
            {
                var high = w.ElementAt(w.Count / 2).Item1;
                medians = (mOld, high);
                stepCount += n - mOld;
            }
            else
            {
                var low = w.ElementAt(w.Count / 2 - 1).Item1;
                var high = w.ElementAt(w.Count / 2).Item1;
                medians = (low, high);
                //w.StepCount = w.StepCount;
            }
        }
    }
 
    void Expansion(int n)
    {
        if (w.Count % 2 == 1)
        {
            if (n >= medians.High)
            {
                medians = (medians.High, medians.High);
                stepCount = stepCount + (n - medians.High);
            }
            else if (n <= medians.Low)
            {
                medians = (medians.Low, medians.Low);
                stepCount = stepCount + (medians.Low - n);
            }
            else
            {
                medians = (n, n);
                //w.StepCount = w.StepCount;
            }
        }
        else
        {
            var mOld = medians.High; // w.Medians.High == w.Medians.Low
            if (n > mOld)
            {
                var high = w.ElementAt(w.Count / 2).Item1;
                medians = (mOld, high);
                stepCount = stepCount + (n - mOld);
            }
            else if (n < mOld)
            {
                var low = w.ElementAt(w.Count / 2 - 1).Item1;
                medians = (low, mOld);
                stepCount = stepCount + (mOld - n);
            }
            else
            {
                medians = (n, n);
                //w.StepCount = w.StepCount;
            }
 
        }
    }
 
}