C++ O(n log n) Using binary indexed tree (Fenwick tree)
\nclass Solution {\npublic:\n    void update(vector<int>&bit,int index,int val)\n    {\n        while(index < bit.size())\n        {\n            bit[index] += 
```\nclass Solution {\npublic:\n    void update(vector<int>&bit,int index,int val)\n    {\n        while(index < bit.size())\n        {\n            bit[index] += val;\n            index += index&(-index);\n        }\n    }\n    int prefix(vector<int>&bit,int index)\n    {\n        int sum = 0;\n        while(index > 0)\n        {\n            sum += bit[index];\n            index -= index&(-index);\n        }\n        return sum;\n    }\n    int suffix(vector<int>&bit,int index)\n    {\n        return prefix(bit,1e5+4)-prefix(bit,index-1);\n    }\n    int numTeams(vector<int>& rating) \n    {\n        vector<int>bitl(100000+5,0);\n        vector<int>bitr(100000+5,0);\n        for(auto r:rating)\n        {\n            update(bitr,r,1);\n        }\n        int ans = 0;\n        for(auto r:rating)\n        {\n            int leftLess = prefix(bitl,r-1);\n            int leftGreat = suffix(bitl,r+1);\n            int rightLess = prefix(bitr,r-1);\n            int rightGreat = suffix(bitr,r+1);\n            update(bitl,r,1);\n            update(bitr,r,-1);\n            ans += (leftLess*rightGreat);\n            ans += (leftGreat*rightLess);\n        }\n        return ans;\n    }\n};\n```
[]