C# Ordered Set + Queue
Complexity\n- Time complexity:\n    - MKAverage(int m, int k): O(1)\n\n    - AddElement(int num):\n        - count < m: O(1)\n        - count == m: O(k + mlogm)
# Complexity\n- Time complexity:\n    - MKAverage(int m, int k): $$O(1)$$\n\n    - AddElement(int num):\n        - count < m: $$O(1)$$\n        - count == m: $$O(k + mlogm)$$\n        - count > m: $$O(logm)$$\n    - CalculateMKAverage(): $$O(1)$$\n\n- Space complexity: $$O(m)$$\n\n# Code\n```\npublic class MKAverage\n{\n    private readonly int m;\n    private readonly int k;\n\n    private readonly Queue<int> q;\n    private readonly List<int> stream;\n\n    private long sum;\n    private long s1;\n    private long s2;\n\n    public MKAverage(int m, int k)\n    {\n        this.m = m;\n        this.k = k;\n\n        q = new Queue<int>();\n        stream = new List<int>();\n\n        sum = 0;\n        s1 = 0;\n        s2 = 0;\n    }\n\n    public void AddElement(int num)\n    {\n        q.Enqueue(num);\n\n        if (stream.Count < m)\n        {\n            stream.Add(num);\n\n            if (stream.Count == m)\n            {\n                stream.Sort();\n\n                for (int i = 0; i < k; i++)\n                {\n                    s1 += stream[i];\n                    s2 += stream[m - 1 - i];\n                }\n            }\n        }\n        else\n        {\n            InsertElement(num);\n            DeleteElement();\n        }\n\n        sum += num;\n    }\n\n    private void InsertElement(int num)\n    {\n        int index = stream.BinarySearch(num);\n        if (index < 0)\n        {\n            index = ~index;\n        }\n\n        stream.Insert(index, num);\n\n        if (index < k)\n        {\n            s1 -= stream[k];\n            s1 += num;\n        }\n        if (index > m - k)\n        {\n            s2 -= stream[m - k];\n            s2 += num;\n        }\n    }\n\n    private void DeleteElement()\n    {\n        int num = q.Dequeue();\n        int index = stream.BinarySearch(num);\n\n        if (index < k)\n        {\n            s1 += stream[k];\n            s1 -= num;\n        }\n        if (index > m - k)\n        {\n            s2 += stream[m - k];\n            s2 -= num;\n        }\n\n        stream.RemoveAt(index);\n        sum -= num;\n    }\n\n    public int CalculateMKAverage()\n    {\n        if (stream.Count < m)\n        {\n            return -1;\n        }\n\n        return (int)((sum - s1 - s2) / (m - 2 * k));\n    }\n}\n```
['Queue', 'Ordered Set', 'C#']