C++ solutions O(n ^ 3), O(n ^ 2) and O(nlogn)
Trivial O(n ^ 3)\n\n\nclass Solution {\n    \n    \npublic:\n    int numTeams(vector<int>& rating) {\n        int r = 0;\n        const int n = rating.size();\n
Trivial O(n ^ 3)\n```\n\nclass Solution {\n    \n    \npublic:\n    int numTeams(vector<int>& rating) {\n        int r = 0;\n        const int n = rating.size();\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < i; ++j) {\n                for (int k = 0; k < j; ++k) {\n                    if ((rating[i] < rating[j] && rating[j] < rating[k]) ||  (rating[i] > rating[j] && rating[j] > rating[k])) {\n                        ++r;\n                    }\n                }\n            }\n        }\n        return r;\n        \n    }\n};\n```\n\nTrivial O(n ^ 2)\n\n```\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        const int n = rating.size();\n        int r = 0;\n        for (int i = 0; i < n; ++i) {\n            int x1 = 0, x2 = 0, y1 = 0, y2 = 0;\n            for (int j = 0; j < n; ++j) {\n                if (j < i) {\n                    if (rating[j] < rating[i]) {\n                        ++x1;\n                    } else {\n                        ++x2;\n                    }\n                } else if (j > i) {\n                    if (rating[j] < rating[i]) {\n                        ++y1;\n                    } else {\n                        ++y2;\n                    }\n                }\n            }\n            r += x1 * y2 + x2 * y1;\n        }\n        return r;\n        \n    }\n};\n```\n\nWith the help of map and tree index array we can achieve O(nlogn):\n\n```\nclass Solution {\n    void update(vector<int> &v, int i, const int d) {\n        for (; i < v.size(); v[i] += d, i += (i & -i));\n    }\n    \n    int presum(const vector<int> &v, int i) {\n        int r = 0;\n        for (; i; r += v[i], i -= (i & -i));\n        return r;\n    }\n    \npublic:\n    int numTeams(vector<int>& rating) {\n        map<int, int> have;\n        for (int x : rating) {\n            have[x];\n        }\n        int n = 0;\n        vector<int> after(rating.size() + 1);\n        for (auto& t : have) { \n            update(after, t.second = ++n, 1);\n        }\n        vector<int> before(n + 1);\n        int r = 0;\n        for (int i = 0; i < n; ++i) {\n            const int x = have[rating[i]], t1 = presum(before, x), t2 = presum(after, x);\n            r += t1 * (n - i - t2) + (i - t1) * (t2 - 1);\n            update(after, x, -1);\n            update(before, x, 1);\n        }\n        return r;\n        \n    }\n};\n```
[]