[C#] solution O(M^2) using List
C# does not have any sorted tree classes that allow duplicate elements. So fast workaround is maintain a sorted List with small optimization for large M.\n\nWe 
C# does not have any sorted tree classes that allow duplicate elements. So fast workaround is maintain a sorted List with small optimization for large M.\n\nWe maintain sorted list of all nums in current sliding window. To maintain expiration of numbers in sliding window we can use queue.\nWhen new number arrives we do two actions:\n1) binarysearch and remove expiring number. Adjust average value. Time is O(logM + M) but usually less\n2) binarysearch and insert new number. Adjust average value. Time is O(logM + M) but usually less\n\nRuntime is ~1.6sec so it barely makes a cut. But its fast and easy implementation if you not comfortable with implementing Trees on your own.\n\n```\npublic class MKAverage {\n    private Queue<int> window = new Queue<int>();\n    private List<int> sorted;\n    private int lowIdx;\n    private int highIdx;\n    private int m;\n    private int k;\n    private long currSum = 0;\n    \n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n        lowIdx = k;\n        highIdx = m - k - 1;\n        sorted = new List<int>(m);\n    }\n    \n    public void AddElement(int num) {\n        var sCount = sorted.Count;\n        if (window.Count == m){\n            var t = window.Dequeue();\n            var tIdx = sorted.BinarySearch(t);\n            if (tIdx <= lowIdx){\n                currSum -= sorted[lowIdx];\n                currSum += sorted[highIdx + 1];\n            } else if (tIdx <= highIdx){\n                currSum -= t;\n                currSum += sorted[highIdx + 1];                \n            }\n\n            sorted.RemoveAt(tIdx);\n        }\n        \n        \n        if (sCount < m - 1){\n\t\t    // no need to sort untill M elements are in the window\n            sorted.Add(num);\n        } else if (sCount == m - 1){\n\t\t    // when first time hitting M elements in window we sort List from here on we maintain sorted order\n            sorted.Add(num);\n            sorted.Sort();\n            for(var i = lowIdx; i <= highIdx; i++){\n                currSum += sorted[i];\n            }\n        } else{\n            var numIdx = sorted.BinarySearch(num);\n            numIdx = numIdx < 0 ? ~numIdx : numIdx;\n            sorted.Insert(numIdx, num); \n            if (numIdx <= lowIdx){\n                currSum -= sorted[highIdx+1];\n                currSum += sorted[lowIdx];\n            } else if (numIdx <= highIdx){\n                currSum -= sorted[highIdx+1];\n                currSum += num;\n            }\n        }\n        \n        window.Enqueue(num);\n        \n    }\n    \n    public int CalculateMKAverage() {\n        return sorted.Count < m ? -1 : (int)(currSum/(m-k-k));\n    }\n}\n\n```
[]