[Python] O(n^3), O(n^2), O(nlogn) solutions
\nfrom sortedcontainers import SortedList\n\nclass Solution:\n\n\t# O(n^3) bruteforce check all the indices\n    def numTeams(self, rating: List[int]) -> int:\n
```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n\n\t# O(n^3) bruteforce check all the indices\n    def numTeams(self, rating: List[int]) -> int:\n        cnt = 0\n        \n        for i in range(len(rating)-2):\n            for j in range(i+1, len(rating)-1):\n                if rating[i] != rating[j]:\n                    for k in range(j+1, len(rating)):\n                        if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):\n                            cnt += 1\n        return cnt \n    \n\t# O(n^2 * k) but k is constant. Dynamic Programming bottom up one pass, it works also for k with higher values\n    def numTeams(self, rating: List[int]) -> int:    \n        def inc_sub(arr, k):\n            dp = [[[0,0] for i in range(len(arr))] for i in range(k)]\n            \n            for i in range(len(arr)): \n                dp[0][i] = [1,1] \n                \n            for cl in range(1, k):\n                for i in range(len(rating)):\n                    for j in range(cl-1, i):\n                        if arr[j] < arr[i]:\n                            dp[cl][i][0] += dp[cl-1][j][0]\n                        if arr[j] > arr[i]:\n                            dp[cl][i][1] += dp[cl-1][j][1]\n            \n            return sum(l1+l2 for l1, l2 in dp[-1])     \n        return inc_sub(rating, 3)\n\n    \n\t# O(n^2 * k) but k is constant. Dynamic Programming bottom up two passes, it works also for k with higher values\n    def numTeams(self, rating: List[int]) -> int:\n        def inc_sub(arr, k):\n            dp = [[0 for i in range(len(arr))] for i in range(k)]\n            \n            for i in range(len(arr)): \n                dp[0][i] = 1\n                \n            for cl in range(1, k):\n                for i in range(len(rating)):\n                    for j in range(cl-1, i):\n                        if arr[j] < arr[i]:\n                            dp[cl][i] += dp[cl-1][j]\n            \n            return sum(dp[-1])     \n        return inc_sub(rating, 3) + inc_sub(rating[::-1], 3)\n\n    \n\t# O(nlogn), keep sorted left and right so we can find the insertion point with binary search. \n    def numTeams(self, rating: List[int]) -> int:\n        \n        def indices(sl, x):\n            return sl.bisect_left(x), len(sl) - sl.bisect_right(x)\n        \n        res = 0\n        \n        left = SortedList()\n        right = SortedList(rating)\n        \n        for x in rating:  \n            right.remove(x)\n            low_left, high_left = indices(left, x)\n            low_righ, high_righ = indices(right, x)\n            res += low_left * high_righ + high_left * low_righ\n            left.add(x)     \n        return res\n```
[]