C# Solution | Easy to understand, Binary search
Intuition\nIt is obvious that we should somehow iterate over all subarrays, sort them and calculate the imbalance number for each of them. However, it is even m
# Intuition\nIt is obvious that we should somehow iterate over all subarrays, sort them and calculate the imbalance number for each of them. However, it is even more obvious that this approach would be very slow.\n\n# Approach\nWhat we can do to optimize the intuitive approach, is to use binary search to find the insert position for each every next element that should be considered. Upon inserting it, we should check if this insertions would cause some new or bread some existing imbalances.\n\nAnd the last thing that should be noted is that we can use the imbalance number of shorter subarrays (as log as they start from the same index) in order to calculate the imbalance number for longer subarrays.\n\n# Complexity\n- Time complexity: $O(n^2*log(n))$\n- Space complexity: $O(n)$\n\n# Code\n```\npublic class Solution {\n    public int SumImbalanceNumbers(int[] nums) {\n        List<int> l = new List<int>(capacity: nums.Length);\n\n        int ans = 0;\n        for (int i = 0; i < nums.Length - 1; i++) {\n            l.Clear();\n\n            int accumulator = 0;\n            for (int j = i; j < nums.Length; j++)\n            {\n                int pos = l.BinarySearch(nums[j]);\n                if (pos < 0) pos = ~pos;\n\n                l.Insert(pos, nums[j]);\n                bool hasNext = pos + 1 < l.Count;\n                bool hasPrev = pos - 1 >= 0;\n\n                if (hasNext && l[pos + 1] - l[pos] > 1) accumulator++;\n                if (hasPrev && l[pos] - l[pos - 1] > 1) accumulator++;\n                if (hasNext && hasPrev && l[pos + 1] - l[pos - 1] > 1) accumulator--;\n\n                ans += accumulator;\n            }\n        }\n\n        return ans;\n    }\n}\n```
['Binary Search', 'Counting', 'C#']