C++ solution, go through all subarrays, one length at a time
\nclass Solution {\npublic:\n  int sumImbalanceNumbers(vector<int>& nums) {\n    int n = nums.size();\n    int tot = 0;\n    vector<int> imbalance(n, 0);\n    v
```\nclass Solution {\npublic:\n  int sumImbalanceNumbers(vector<int>& nums) {\n    int n = nums.size();\n    int tot = 0;\n    vector<int> imbalance(n, 0);\n    vector<set<int>> btrees(n);\n    for (int i = 0; i < n; ++i) {\n      btrees[i].insert(nums[i]);\n    }\n    for (int l = 2; l <= n; ++l) {\n      for (int i = l - 1; i < n; ++i) {\n        int next = -1, prev = -1;\n        auto lb = btrees[1 + i - l].lower_bound(nums[i]);\n        if (lb != btrees[1 + i - l].end()) {\n          next = *lb;\n        }\n        if (lb != btrees[1 + i - l].begin()) {\n          prev = *--lb;\n        }\n        int extraImbalance = 0;\n        if (next != -1 && prev != -1) {\n          if (abs(next - prev) > 1) {\n            extraImbalance--;\n          }\n        }\n        if (next != -1 && abs(next - nums[i]) > 1) {\n          extraImbalance++;\n        }\n        if (prev != -1 && abs(nums[i] - prev) > 1) {\n          extraImbalance++;\n        }\n        imbalance[1 + i - l] += extraImbalance;\n        btrees[1 + i - l].insert(nums[i]);\n        tot += imbalance[1 + i - l];\n      }\n    }\n    return tot;\n  }\n};\n```
[]