There are n soldiers standing in a line. Each soldier is assigned a unique rating value.
You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).
 
Example 1:
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:
Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:
Input: rating = [1,2,3,4]
Output: 4

 
Constraints:

n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5

Difficulty: interview

Starter code:

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        

Solutions:
class Solution:
    def increment_index(self, nums, index):
        index += 1
        while index < len(nums):
            nums[index] += 1
            index += (index & -index)

    def prefix_sum(self, nums, index):
        index += 1
        current_sum = 0
        while index > 0:
            current_sum += nums[index]
            index -= (index & -index)
        return current_sum

    def numTeams(self, rating):
        if len(rating) < 3:
            return 0

        n = len(rating)
        sorted_nums = rating.copy()
        sorted_nums.sort()

        index = {}
        for i in range(n):
            index[sorted_nums[i]] = i

        fenwick_tree = [0] * (len(sorted_nums) + 1)

        lesser_before = [0] * n
        for i in range(n):
            rate_i = rating[i]
            index_i = index[rate_i]
            lesser_before[i] = self.prefix_sum(fenwick_tree, index_i)
            self.increment_index(fenwick_tree, index[rating[i]])

        for i in range(len(fenwick_tree)):
            fenwick_tree[i] = 0

        lesser_after = [0] * n
        for i in range(n - 1, -1, -1):
            rate_i = rating[i]
            index_i = index[rate_i]
            lesser_after[i] = self.prefix_sum(fenwick_tree, index_i)
            self.increment_index(fenwick_tree, index[rating[i]])

        num_teams = 0
        for i in range(n - 1):
            num_teams += lesser_before[i] * (n - 1 - i - lesser_after[i])
            num_teams += (i - lesser_before[i]) * lesser_after[i]

        return num_teams


class FenwickTree:
    def __init__(self, nums_node: int):
        self.nums_node = nums_node
        self.arr = [0] * nums_node
        self.total = 0

    def get_sum(self, index: int):
        if index < 0:
            return self.total - self.get_sum(~index)
        if index >= self.nums_node:
            return self.total
        result = 0
        while index >= 0:
            result += self.arr[index]
            index = (index & (index + 1)) - 1
        return result

    def update(self, index: int, delta: int):
        self.total += delta
        while index < self.nums_node:
            self.arr[index] += delta
            index = index | (index + 1)


class Solution:
    def numTeams(self, rating: list) -> int:
        count = 0
        rating_len = len(rating)

        sort_map = {r: i for i, r in enumerate(sorted(rating))}

        left_tree = FenwickTree(rating_len)
        right_tree = FenwickTree(rating_len)

        for rat in rating:
            right_tree.update(sort_map[rat], 1)

        for rat in rating:
            index = sort_map[rat]
            right_tree.update(index, -1)
            count += (left_tree.get_sum(index) *
                      right_tree.get_sum(~index))
            count += (left_tree.get_sum(~index) * right_tree.get_sum(index))
            left_tree.update(index, 1)

        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        res = 0
        
        for i in range(1, len(rating) -1):
            l_small, l_great = 0,0
            for j in range(i):
                if rating[i]<rating[j]:
                    l_great += 1
                elif rating[i]>rating[j]:
                    l_small+=1
                    
            r_small, r_great = 0,0
            for k in range(i+1, len(rating)):
                if rating[i]>rating[k]:
                    r_small+=1
                elif rating[k]>rating[i]:
                    r_great+=1
                    
            res += l_small*r_great
            res += l_great*r_small
            
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:

        
        count = 0
        
        for i in range(len(rating)):
            map_g = {}
            map_l = {}
            for j in range(i + 1, len(rating)):
                count += sum([k < rating[j] for k in list(map_l.keys())])+ sum([k > rating[j] for k in list(map_g.keys())])
                if rating[i] < rating[j]:
                    map_l[rating[j]] = map_l.get(rating[j], 0) + 1
                if rating[i] > rating[j]:
                    map_g[rating[j]] = map_g.get(rating[j], 0) + 1
        return count


# x x x x x
#   i   j

# xi != xj

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            firstChoice = rating[i]
            for j in range(i + 1, len(rating)):
                secondChoice = rating[j]
                for k in range(j + 1, len(rating)):
                    thirdChoice = rating[k]
                    if (firstChoice < secondChoice < thirdChoice) or (firstChoice > secondChoice > thirdChoice):
                        count += 1
        return count        
            


import itertools

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return sum(
            1
            for ri, rj, rk in itertools.combinations(rating, 3)
            if (ri < rj < rk) or (ri > rj > rk)
        )


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cpt = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                if rating[j]>rating[i]:
                    for k in range(j+1,len(rating)):
                        if rating[k]>rating[j]:
                            cpt += 1
                else:
                    for k in range(j+1,len(rating)):
                        if rating[k]<rating[j]:
                            cpt += 1
        return cpt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return len([1 for i,j,k in itertools.combinations_with_replacement(rating,3) if i<j<k or i>j>k])

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in rating:
            for j in rating[rating.index(i)+1:]:
                for k in rating[rating.index(j)+1:]:
                    if i < j < k or k < j < i:
                        cnt += 1
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(len(rating)):
            fst = rating[i]
            for j in range(i + 1, len(rating)):
                scn = rating[j]
                if fst == scn:
                    break
                a = fst > scn
                for k in range(j + 1, len(rating)):
                    thr = rating[k]
                    if scn == thr:
                        break
                    
                    if a and scn > thr:
                        cnt = cnt + 1
                        
                    if not a and scn < thr:
                        cnt = cnt + 1
                        
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
       
        def getTeams(k, l, prev = None, asc=True):
            if (k>len(l)):
                return 0
            if ((prev is None) & (k == 1)):
                return len(l)
            if (k == 1):
                if asc: 
                    teamCount = sum([x>prev for x in l])
                else:
                    teamCount = sum([x<prev for x in l])
            else:
                teamCount = 0
                larger_x = True
                if prev is not None:
                    larger_x = l[0]>prev
                    
                    
                if ((larger_x == asc) | (prev is None)):
                    #include this one
                    teamCount +=getTeams(k-1, l[1:], l[0], asc)
                    #exclude this one
                teamCount +=getTeams(k, l[1:], prev, asc)
                    
                    
                if(0):    
                    if asc:
                        if (larger_x | (prev is None)):
                        #include this one
                            teamCount +=getTeams(k-1, l[1:], l[0], asc)
                        #exclude this one
                        teamCount +=getTeams(k, l[1:], prev, asc)

                    else:
                        if (larger_x == False | (prev is None)):
                            #print(prev, l[0], larger_x)
                        #include this one
                            teamCount +=getTeams(k-1, l[1:], l[0], asc)
                        #exclude this one
                        teamCount +=getTeams(k, l[1:], prev, asc)
                #print('getTeams: ', k, l, prev, asc,'   result: ', teamCount)
            return teamCount
        
        return getTeams(3, rating, None, True) + getTeams(3, rating, None, False)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
       
        def getTeams(k, l, prev = None, asc=True):
            if (k>len(l)):
                return 0
            if ((prev is None) & (k == 1)):
                return len(l)
            if (k == 1):
                if asc: 
                    teamCount = sum([x>prev for x in l])
                else:
                    teamCount = sum([x<prev for x in l])
            else:
                teamCount = 0
                larger_x = True
                if prev is not None:
                    larger_x = l[0]>prev
                    
                    
                if ((larger_x == asc) | (prev is None)):
                    #include this one
                    teamCount +=getTeams(k-1, l[1:], l[0], asc)
                    #exclude this one
                teamCount +=getTeams(k, l[1:], prev, asc)
                    
            return teamCount
        
        return getTeams(3, rating, None, True) + getTeams(3, rating, None, False)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        l = len(rating)
        res = 0
        for i, vi in enumerate(rating):
            if i >= l - 2:
                break
                
            for j, vj in enumerate(rating[i+1:]):
                if j >= l - 1:
                    break
                
                for k, vk in enumerate(rating[i+j+1:]):
                    if (vi < vj and vj < vk) or (vi > vj and vj > vk):
                        res += 1
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n=len(rating)
        teams=0
        for i in range(1,n-1):
            lt_l,lt_r,gt_l,gt_r=0,0,0,0
            for j in range(n):
                if rating[i]<rating[j]:
                    if i<j:
                        gt_r+=1
                    else:
                        gt_l+=1
                elif rating[i]>rating[j]:
                    if i<j:
                        lt_r+=1
                    else:
                        lt_l+=1
            teams+=lt_l*gt_r+gt_l*lt_r
        
        # for i in range(n):
        #     for k in range(i+2,n):
        #         if rating[i]<rating[k]:
        #             teams+=len([r for r in rating[i+1:k] if rating[i]<r<rating[k]])
        #         else:
        #             teams+=len([r for r in rating[i+1:k] if rating[i]>r>rating[k]])
        
        # for i in range(n):
        #     for j in range(i+1,n):
        #         for k in range(j+1,n):
        #             if rating[i]<rating[j]<rating[k] or rating[i] > rating[j] > rating[k]:
        #                 teams+=1
        return teams


class Solution:
    def numTeams(self, r: List[int]) -> int:
        ct=0
        for i in range(len(r)):
            for j in range(i+1, len(r)):
                b=-1
                if r[i]>r[j]:
                    b = 1 # need number id dec order
                else : b = 0 # nedd number in asc order
                for k in range(j+1, len(r)):
                    if b == 1 and r[k]<r[j]:
                        #print(r[i],r[j],r[k])
                        ct += 1
                        continue
                    if b == 0 and r[k]>r[j]:
                        #print(r[i],r[j],r[k])
                        ct += 1
                        continue
        return ct
                        
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
       
        def getTeams(k, l, prev = None, asc=True):
            if (k>len(l)):
                return 0
            if ((prev is None) & (k == 1)):
                return len(l)
            if (k == 1):
                if asc: 
                    teamCount = sum([x>prev for x in l])
                else:
                    teamCount = sum([x<prev for x in l])
            else:
                teamCount = 0
                larger_x = True
                if prev is not None:
                    larger_x = l[0]>prev
                    
                if asc:
                    if (larger_x | (prev is None)):
                    #include this one
                        teamCount +=getTeams(k-1, l[1:], l[0], asc)
                    #exclude this one
                    teamCount +=getTeams(k, l[1:], prev, asc)
                        
                else:
                    if (larger_x == False | (prev is None)):
                        #print(prev, l[0], larger_x)
                    #include this one
                        teamCount +=getTeams(k-1, l[1:], l[0], asc)
                    #exclude this one
                    teamCount +=getTeams(k, l[1:], prev, asc)
            #print('getTeams: ', k, l, prev, asc,'   result: ', teamCount)
            return teamCount
        
        return getTeams(3, rating, None, True) + getTeams(3, rating, None, False)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cpt = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                if rating[j]>rating[i]:
                    for k in range(j+1,len(rating)):
                        if rating[k]>rating[j]:
                            cpt += 1
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                if rating[j]<rating[i]:
                    for k in range(j+1,len(rating)):
                        if rating[k]<rating[j]:
                            cpt += 1
        return cpt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ret, n = 0, len(rating)
        for i in range(n-2):
            for j in range(i+1, n-1):
                if rating[j] > rating[i]:
                    for k in range(j+1, n):
                        if rating[k] > rating[j]:
                            ret += 1
        for i in range(n-2):
            for j in range(i+1, n-1):
                if rating[j] < rating[i]:
                    for k in range(j+1, n):
                        if rating[k] < rating[j]:
                            ret += 1
        return ret

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        num_teams = 0
        for i,r1 in enumerate(rating):
            for j,r2 in enumerate(rating[(i+1):]):
                for k,r3 in enumerate(rating[(i+j+1):]):
                    num_teams += ((r1 < r2 < r3) or (r1 > r2 > r3))
        return num_teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        incr = True
        for i in range(len(rating)-1):
                
            for j in range(i+1, len(rating)):
                if rating[i] < rating[j]: incr = True
                elif rating[i] > rating[j]: incr = False
                else: continue
                    
                for k in range(j+1, len(rating)):
                    if ((rating[j] < rating[k] and incr) or 
                        (rating[j] > rating[k] and not incr)):
                            count += 1
        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        numT = 0 
        
        if (len(rating) < 3): 
            return 0 
        
        blah = list(range(len(rating)))
        
        for first_idx in blah[:-2]:
            first = rating[first_idx]

            for second_idx in blah[first_idx:]:
                second = rating[second_idx]
                
                for third_idx in blah[second_idx:]:
                    third = rating[third_idx]
                    if (first < second and second < third):
                        numT += 1
                    if (first > second and second > third):
                        numT += 1
                        
        return numT


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        team = 0
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)-1):
                if rating[j] > rating[i]:
                    for k in range(j+1, len(rating)):
                        if rating[k] > rating[j]:
                            team = team + 1
                elif rating[j] < rating[i]:
                    for k in range(j+1, len(rating)):
                        if rating[k] < rating[j]:
                            team = team + 1
        return team

class Solution:
    def numTeams(self, rating: List[int]) -> int:

        p = 0 
        res = 0 
        while p < len(rating):
            left_less = sum([1 for i in range(p) if rating[i] < rating[p]])
            right_more = sum([1 for i in range(p+1, len(rating)) if rating[i] > rating[p]])
            
            left_more = sum([1 for i in range(p) if rating[i] > rating[p]])
            right_less = sum([1 for i in range(p+1, len(rating)) if rating[i] < rating[p]])
            
            res += left_less * right_more + left_more * right_less
            
            p += 1
            
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        index = {}
        
        n = len(rating)
        for i in range(n):
            index[rating[i]] = i
        rating.sort()
        count = 0
        for i in range(n):
            for j in range(i+1,n):
                if index[rating[i]] < index[rating[j]]:
                    for k in range(j+1,n):
                        if index[rating[j]] < index[rating[k]]:
                            count += 1

        rating.sort(reverse=True)
        for i in range(n):
            for j in range(i+1,n):
                if index[rating[i]] < index[rating[j]]:
                    for k in range(j+1,n):
                        if index[rating[j]] < index[rating[k]]:
                            count += 1

        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i, r_i in enumerate(rating):
            for j, r_j in enumerate(rating[i+1:], i+1):
                for k, r_k in enumerate(rating[j+1:], j+1):
                    count += r_i < r_j < r_k or r_i > r_j > r_k
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return len(Solution.generate_teams(rating))
    
    @staticmethod
    def generate_teams(rating):
        teams = []
        rating_copy = rating
        negative_rating = [-num for num in rating]
        
        for rating in (rating_copy, negative_rating):
            for i in range(len(rating)):
                curr_first_soldier = rating[i]
                for j in range(i + 1, len(rating)):
                    curr_second_soldier = rating[j]
                    if i != j and curr_second_soldier > curr_first_soldier:
                        for k in range(j + 1, len(rating)):
                            curr_third_soldier = rating[k]
                            if k != j and curr_third_soldier > curr_second_soldier:
                                teams.append((curr_first_soldier, curr_second_soldier, curr_third_soldier))
        return teams
    
class SolutionTest:
    @staticmethod
    def test_generate_teams():
        test_ratings = [2, 3, 7, 1, 8, 9]
        
        actual_teams = [(2,3,7),(2,3,8),(2,3,9),(2,7,8),(2,7,9),(2,8,9),(3,7,8),(3,7,9),(3,8,9),(7,8,9),(1,8,9)]
        expected_teams = Solution.generate_teams(test_ratings)
        
        return actual_teams == expected_teams
    
print(SolutionTest.test_generate_teams())

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        import itertools
        return len([1 for i,j,k in itertools.combinations(rating,3) if i>j>k or i<j<k])

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        for pt1 in range(len(rating)-2):
            for pt2 in range(pt1+1,len(rating)-1):
                if rating[pt1]<rating[pt2]:
                    for pt3 in range(pt2+1,len(rating)):
                        if rating[pt2]<rating[pt3]:
                            ans += 1
                if rating[pt1]>rating[pt2]:
                    for pt3 in range(pt2+1,len(rating)):
                        if rating[pt2]>rating[pt3]:
                            ans += 1
                            
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res=0
        record = []
        rec = []
        for i in range(0,len(rating)):
            record.append([])
            for j in range(i+1):
                record[i].append(None)
            for j in range(i+1,len(rating)):
                if rating[j] > rating[i]:
                    record[i].append(True)
                elif rating[j] < rating[i]:
                    record[i].append(False)
        for i in range(0,len(rating)-1):

            for j in range(i+1,len(rating)):
                if record[i][j]:
                    for k in range(j+1,len(rating)):
                        if record[j][k]:
                            res += 1
                            rec.append((rating[i],rating[j],rating[k]))
                elif record[i][j]==False:
                    for k in range(j+1,len(rating)):
                        if record[j][k]==False:
                            res += 1
                            rec.append((rating[i], rating[j], rating[k]))
        
        return res


class Solution:
    def numTeams(self,rating):
        return sum(x<y<z or x>y>z for x,y,z in combinations(rating,3))

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        if len(rating) > 2:
            for i in rating[:-2]:
                for j in rating[(rating.index(i)+1):-1]:
                    for k in rating[(rating.index(j)+1):]:
                        if (i < j) and (j < k):
                            count += 1
                        elif (i > j) and (j > k):
                            count += 1
                        else:
                            count += 0
        else:
            count = 0
        return count
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(0, len(rating)-2):
            if rating[i] == rating[i+1]:
                continue
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if rating[i] > rating[j]:
                        if rating[j] > rating[k]:
                            cnt += 1
                    elif rating[j] < rating[k]:
                        cnt += 1
        return cnt 

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)):
    
            for j in range(i+1,len(rating)):
        
                if rating[i]<rating[j]:
                    for k in range(j+1,len(rating)):
                        if rating[j]<rating[k]:
                            count+=1
        
                elif rating[i]>rating[j]:
                    for k in range(j+1,len(rating)):
                        if rating[j]>rating[k]:
                            count+=1
        return count 

from itertools import combinations
class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(0, len(rating)-2):
            if rating[i] == rating[i+1]:
                continue
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if rating[i] > rating[j]:
                        if rating[j] > rating[k]:
                            cnt += 1
                    elif rating[j] < rating[k]:
                        cnt += 1
        return cnt              
        
        
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        for i in range(len(rating)):
            a = rating[i]
            for j in range(i+1, len(rating)):
                b = rating[j]
                for k in range(j+1, len(rating)):
                    c = rating[k]
                    if a < b < c or a > b > c:
                        ans += 1
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i, r_i in enumerate(rating):
            for j, r_j in enumerate(rating[i+1:], i+1):
                if r_i == r_j:
                    continue

                if r_i < r_j:
                    for k, r_k in enumerate(rating[j+1:], j+1):
                        count += r_j < r_k
                else:
                    for k, r_k in enumerate(rating[j+1:], j+1):
                        count += r_j > r_k
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:

        p = 0 
        res = 0 
        while p < len(rating):
            less = sum([1 for i in range(p) if rating[i] < rating[p]])
            more = sum([1 for i in range(p+1, len(rating)) if rating[i] > rating[p]])
            
            more1 = sum([1 for i in range(p) if rating[i] > rating[p]])
            less1 = sum([1 for i in range(p+1, len(rating)) if rating[i] < rating[p]])
            
            res += less * more + more1 * less1
            
            p += 1
            
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        
        
        #Get the first element at rating[base]
        for base in range(len(rating)):
            second = base + 1
            
            while second  < len(rating):
                #If the second element is greater than the first, look for the third after that position
                if rating[second] > rating[base]:
                    third = second + 1
                    
                    while third < len(rating):
                        if rating[third] > rating[second]:
                            teams += 1
                    
                        #print(base, second, third, rating[base], rating[second], rating[third])
                        third += 1
                    
                second += 1
        
        for base in range(len(rating)):
            second = base + 1
            
            while second < len(rating):
                
                if rating[second] < rating[base]:
                    third = second + 1
                    
                    while third < len(rating):
                        if rating[third] < rating[second]:
                            teams += 1
                        
                        third += 1
                second += 1
                
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        
        
        teams: int = 0
        for i, s1 in enumerate(rating):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    s2 = rating[j]
                    s3 = rating[k]
                    if s1 > s2 > s3 or s1 < s2 < s3:
                        teams += 1
        
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        possibleTeams = []
        temp = []
        for i in range(len(rating)):
            soldier_i = rating[i]
            for j in range(i+1, len(rating)):
                soldier_j = rating[j]
                if soldier_j > soldier_i:
                    increasing = True
                else:
                    increasing = False
                for k in range(j+1, len(rating)):
                    soldier_k = rating[k]
                    if increasing and soldier_k > soldier_j:
                        possibleTeams.append((soldier_i, soldier_j, soldier_k))
                    if increasing == False and soldier_k < soldier_j:
                        possibleTeams.append((soldier_k, soldier_j, soldier_i))
        return len(possibleTeams)


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        sayac = 0
        for i in range(len(rating)):
            temp1 = rating[i]
            for j in range(int(i+1),len(rating)):
                temp2 = rating[j]
                for k in range(int(j+1),len(rating)):
                    temp3 = rating[k]

                    if temp1 > temp2 and temp2 > temp3:
                        sayac+=1
                    if temp3 > temp2 and temp2 > temp1:
                        sayac+=1    
        return sayac


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        l = len(rating)
        for i in range(0, l - 2):
            for j in range(i + 1, l - 1):
                res += len([x for x in rating[j+1:] if (rating[j] < x) == (rating[i] < rating[j])])

        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        if len(rating) < 3:
            return teams
        # rating = [2,5,3,4,1]
        # at each index, i want to see if the following numbers have at least 2 increasing or 2 decreasing
        for i in range(len(rating)):
            first = rating[i]
            for j in range(i + 1, len(rating)):
                second = rating[j]
                for k in range(j + 1, len(rating)):
                    third = rating[k]
                    if first > second and second > third:
                        teams += 1
                    if first < second and second < third:
                        teams += 1
                        
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        
        
        #Get the first element at rating[base]
        for base in range(len(rating) - 2):
            second = base + 1
            
            while second  < len(rating):
                #If the second element is greater than the first, look for the third after that position
                if rating[second] > rating[base]:
                    third = second + 1
                    
                    while third < len(rating):
                        if rating[third] > rating[second]:
                            teams += 1
                    
                        #print(base, second, third, rating[base], rating[second], rating[third])
                        third += 1
                    
                second += 1
        
        for base in range(len(rating)):
            second = base + 1
            
            while second < len(rating):
                
                if rating[second] < rating[base]:
                    third = second + 1
                    
                    while third < len(rating):
                        if rating[third] < rating[second]:
                            teams += 1
                        
                        third += 1
                second += 1
                
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        combos = 0

        for index, numba in enumerate(rating[:-2]):
            for numbay in rating[index+1:-1]:
                for numbaz in rating[rating.index(numbay)+1:]:
                    # print(\"numba:\", numba, \"numbay:\", numbay, \"numbaz:\", numbaz)
                    if numba < numbay and numbay < numbaz:
                        combos += 1
                    elif numba > numbay and numbay > numbaz:
                        combos += 1

        return combos

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        N = len(rating)
        ans = 0
        for i in range(N):
            for j in range(i+1, N):
                for k in range(j+1, N):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        ans += 1
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for a, soldier_1 in enumerate(rating):
            for b, soldier_2 in enumerate(rating[a+1:]):
                for c, soldier_3 in enumerate(rating[a+b+1:]):
                        if soldier_1 < soldier_2 < soldier_3:
                            count += 1
                        if soldier_1 > soldier_2 > soldier_3:
                            count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        temp_list = []
        temp1 = 0
        temp2 = 0
        for i in range(0,len(rating)):
            temp1 = rating[i]
            for j in range(i+1,len(rating)):
                if rating[j]>temp1:
                    temp2 = rating[j]
                    for k in range(j+1,len(rating)):
                        if rating[k] > temp2:
                            temp_list.append([temp1,temp2,rating[k]])
            for j in range(i+1,len(rating)):
                if rating[j]<temp1:
                    temp2 = rating[j]
                    for k in range(j+1,len(rating)):
                        if rating[k] < temp2:
                            temp_list.append([temp1,temp2,rating[k]])
        return len(temp_list)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        resultCounter = 0
        n = len(rating)
        for i in range(n-2):
            for j in range(i, n):
                for k in range (j, n):
                    if rating[k] < rating[j] < rating[i] or rating[k] > rating[j] > rating[i]:
                        resultCounter +=1
        return resultCounter
                    
                    
                    
                    
                


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt=0
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if rating[i]>rating[j]>rating[k] or rating[i]<rating[j]<rating[k]:
                        cnt += 1
                        # print(i, j, k)
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        n = len(rating)
        num_valid_teams = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1,n):
                    if (rating[i]>rating[j]>rating[k]) or (rating[i]<rating[j]<rating[k]):
                        num_valid_teams += 1
                        
        return num_valid_teams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        count += 1
        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        counter = 0
        while len(rating) > 0:
            r = rating.pop(0)
            # print(r)
            counter += countDown(rating, r, 1)
            counter += countUp(rating, r, 1)
        return counter
    
def countUp(rating, value, num_in_team):
    # print(f'countUp({rating}, {value}, {num_in_team}):')
    if len(rating) == 0:
        return 0
    counter = 0
    for i, num in enumerate(rating):
        if  num > value and num_in_team == 2:
            # print(f'{num} is larger than {value} and tahts a team')
            counter += 1
        elif num > value:
            # print(f'{num} is larger than {value}')
            counter += countUp(rating[i:], num, 2)
    # print(f'returning counter with value {counter}')
    return counter

def countDown(rating, value, num_in_team):
    # print(f'countDown({rating}, {value}, {num_in_team}):')
    if len(rating) == 0:
        return 0
    counter = 0
    for i, num in enumerate(rating):
        if  num < value and num_in_team == 2:
            # print(f'{num} is smaller than {value} and tahts a team')
            counter += 1
        elif num < value:
            counter += countDown(rating[i:], num, 2)
    # print(f'returning counter with value {counter}')
    return counter


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        r = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        r += 1
        return r

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt=0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        cnt+=1
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:

        
        elm_less_than_cur_to_left,elm_less_than_cur_to_right, elm_greater_than_cur_to_left, elm_greater_than_cur_to_right = [0]*len(rating),[0]*len(rating), [0]*len(rating), [0]*len(rating)
        
        
        
        
        i = 0 
        res = 0
        
        while i < len(rating):
            k = i-1
            while k >=0:
                if rating[i] > rating[k]:
                    elm_less_than_cur_to_left[i] += 1
                
                elif rating[i] < rating[k]:
                    elm_greater_than_cur_to_left[i] += 1
                k-=1
            
            k = i +1
            while k < len(rating):
                if rating[i] > rating[k]:
                    elm_less_than_cur_to_right[i] += 1
                
                elif rating[i] < rating[k]:
                    elm_greater_than_cur_to_right[i] += 1
                k+=1
            
            i+=1
        # print(elm_less_than_cur_to_left,elm_less_than_cur_to_right, elm_greater_than_cur_to_left, elm_greater_than_cur_to_right ) 
        for i in range(0, len(rating)):
            res+= (elm_less_than_cur_to_left[i] * elm_greater_than_cur_to_right[i]) + (elm_less_than_cur_to_right[i] *elm_greater_than_cur_to_left[i])
            
        return res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        n = len(rating)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        cnt += 1
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        final = 0
        n = len(rating)
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    #print(rating[i] , rating[j],rating[k])
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        final += 1
        return final

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c=0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        c+=1
        return c

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c=0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        c+=1
        return c

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        ct = 0
        
        if n<3:
            return 0
        
        for i in range(n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                    #print(rating[i],rating[j],rating[k])
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        ct+=1
        #print(out)
        return ct

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c = 0
        i, j, k = (0,0,0)
        n = len(rating)
        
        for i in range(0, n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j+ 1, n):
                    if rating[i] > rating[j]:
                        break
                    if rating[i] < rating[j] < rating[k]:
                        c += 1
        
        for i in range(0, n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j+ 1, n):
                    if rating[i] < rating[j]:
                        break
                    if rating[i] > rating[j] > rating[k]:
                        c += 1
        return c
                        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
       
    
        count = 0
        
        for i in range(0, len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        count += 1
                        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        l = len(rating)
        for i in range(l):
            for j in range(i+1,l):
                for k in range(j+1,l):
                    if rating[i] < rating[j] < rating[k] : 
                        count += 1
                    elif rating[i] > rating[j] > rating[k]:
                        count += 1
                        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        count = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    if(rating[i] < rating[j] < rating[k]):
                        count += 1
                    elif(rating[i] > rating[j] > rating[k]):
                        count += 1
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        number_of_teams = 0
        
        if len(rating) < 3:
            return 0
        else:
            for i in range(0, len(rating)):
                for j in range(i + 1, len(rating)):
                    for k in range(j + 1, len(rating)):
                        if (rating[i] < rating[j] and rating[j] < rating[k]) or (rating[i] > rating[j] and rating[j] > rating[k]):
                            number_of_teams += 1
        
        return number_of_teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        num_teams = 0
        greater_than = [0] * n
        less_than = [0] * n
        for left in range(n - 1, -1, -1):
            for right in range(left+1, n):
                if rating[right] > rating[left]:
                    greater_than[left] += 1
                    num_teams += greater_than[right]
                else:
                    less_than[left] += 1
                    num_teams += less_than[right]
        return num_teams
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        
        def dfs(i: int, cur_len:int, last_elem: int, flag: str):
            nonlocal result
            if cur_len == 3:
                result += 1
                return
            
            for x in range(i, len(rating)):
                if flag == 'l':
                    if rating[x] > last_elem:
                        dfs(x + 1, cur_len + 1, rating[x], 'l')
                elif flag == 's':
                    if rating[x] < last_elem:
                        dfs(x + 1, cur_len + 1, rating[x], 's')
                        
        for i in range(len(rating) - 1):
            dfs(i + 1, 1, rating[i], 'l')
            dfs(i + 1, 1, rating[i], 's')
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if rating[i] < rating[j] < rating[k]:
                        count += 1
                    elif rating[i] > rating[j] > rating[k]:
                        count += 1
        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        N = len(rating)
        res = 0
        for i in range(N):
            for j in range(i + 1, N):
                for k in range(j + 1, N):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        res += 1
        
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        combos = 0

        for index, numba in enumerate(rating[:-2]):
            for indexy, numbay in enumerate(rating[index+1:-1]):
                for numbaz in rating[rating.index(numbay)+1:]:
                    # print(\"numba:\", numba, \"numbay:\", numbay, \"numbaz:\", numbaz)
                    if numba < numbay and numbay < numbaz:
                        combos += 1
                    elif numba > numbay and numbay > numbaz:
                        combos += 1

        return combos

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        count += 1
        return count
        
        
        
        
        
        
        # for i in range(len(rating) - 2):
        #     for j in range(i + 1, len(rating) -1):
        #         for k in range(i + 2, len(rating)):
        #             if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
        #                 count += 1
        # return count
    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if(rating[i]>rating[j] and rating[j]>rating[k]):
                        count+=1
                    elif(rating[i]<rating[j] and rating[j]<rating[k]):
                        count+=1
        return(count)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if(rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]):
                        count += 1
        return count                


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        count = 0
        for i in range(0,n):
            for j in range(i,n):
                    for k in range(j,n):
                        if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                                count += 1
        return(count)

class Solution:
    def numTeams(self, rating) -> int:
        n = len(rating)
        ans = 0
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if rating[i] < rating[j] < rating[k]:
                        ans += 1
                    if rating[i] > rating[j] > rating[k]:
                        ans += 1

        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        output = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if rating[i] > rating[j] > rating[k]:
                        output += 1
                    if rating[i] < rating[j] < rating[k]:
                        output += 1
        return output

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        def helper(rating):
            
            resDict = {}
            res = 0
            for i in range(len(rating)):
                for j in range(i, len(rating)):
                    if rating[i] > rating[j]:
                        resDict[i] = resDict.get(i, 0) + 1

            for i in range(len(rating)):
                for j in range(i, len(rating)):
                    if rating[i] > rating[j]:
                        res += resDict.get(j, 0)
            return res
        return helper(rating) + helper(rating[::-1])            
        
                
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n=len(rating)
        teams=0
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    if rating[i]<rating[j]<rating[k] or rating[i] > rating[j] > rating[k]:
                        teams+=1
        return teams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c = 0
        i, j, k = (0,0,0)
        n = len(rating)
        for i in range(0, n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j+ 1, n):
                    if rating[i] > rating[j]:
                        break
                    if rating[i] < rating[j] < rating[k]:
                        c += 1
        for i in range(0, n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j+ 1, n):
                    if rating[i] < rating[j]:
                        break
                    if rating[i] > rating[j] > rating[k]:
                        c += 1
        return c
                        


class Solution:
    def numTeams(self, s: List[int]) -> int:
        count = 0
        if len(s) < 3:
            return 0
        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                for k in range(j + 1, len(s)):
                    if s[i] < s[j] and s[j] < s[k]:
                        count += 1
                    if s[i] > s[j] and s[j] > s[k]:
                        count += 1
        return count   

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        total = 0
        for i in range(n-2):
            for j in range(i + 1, n-1):
                for k in range(j+1, n):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        total += 1
                    elif rating[i] > rating[j] and rating[j] > rating[k]:
                        total += 1
        
        return total
#         n = len(rating)
#         grid = [[0 for i in range(n)] for i in range(n)]
        
#         for win in range(3, n+1):
#             for start in range(n - win + 1):
#                 end = start + win - 1
#                 count = 0
#                 for num in rating[start+1: start + win-1]:
                    
#                     if rating[start] < num and rating[end] > num:
#                         count += 1
#                         print(rating[start], num, rating[end])
#                 print(count)
#                 grid[start][end] = grid[start + 1][end] + grid[start][end-1] + count
        
#         ascend = grid[0][n-1]
        
#         for i in range(n):
#             for j in range(n):
#                 grid[i][j] = 0
                
                
#         for win in range(3, n+1):
#             for start in range(n - win + 1):
#                 end = start + win - 1
#                 count = 0
#                 for num in rating[start+1: start + win-1]:
                    
#                     if rating[start] > num and rating[end] < num:
#                         count += 1
#                         print(rating[start], num, rating[end])
                
#                 grid[start][end] = grid[start + 1][end] + grid[start][end-1] + count
        
#         descend = grid[0][n-1]
        
#         print(ascend)
#         print(descend)
        
#         return ascend + descend


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        new=sorted(rating)
        if new==rating:
            return len(rating)
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if (rating[i] < rating[j] and rating[j] < rating[k]) or (rating[i] > rating[j] and rating[j] > rating[k]):
                        count=count+1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        length = len(rating)
        if length < 3:
            return 0
        
        for i in range(length):
            for j in range(i+1, length):
                for k in range(j + 1, length):
                    if (rating[i] > rating[j] > rating[k]) or (rating[i] < rating[j] < rating[k]):
                        count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        
        for i in range(len(rating)):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        count +=1
                    elif rating[i] > rating[j] and rating[j] > rating[k]:
                        count +=1
        
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        count = 0
        
        n = len(rating)
        m = 3
        
        for i in range(n-2):
            
            for j in range(i+1, n-1):
                
                for k in range(j+1, n):
                    
                    if rating[i] < rating[j] and rating[j]<rating[k]:
                        count += 1
                    elif rating[i] > rating[j] and rating[j] > rating[k]:
                        count +=1
                    else:
                        continue
                        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        l = len(rating)
        c = 0
        for i in range(l):
            for j in range(i+1,l):
                for k in range(j+1,l):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        c += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        c += 1     
        return c


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        lstcount=0
        for i in range(0,len(rating)-2):              
           for j in range(i+1,len(rating)-1):       
             for k in range(j+1,len(rating)):
                 if ((rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k])):
                    lstcount=lstcount+1
        return lstcount

class Solution:
    def numTeams(self, r: List[int]) -> int:
        s=0
        for i in range(len(r)):
            a=0
            b=0
            c=0
            d=0
            for j in range(0,i):
                if r[j]<r[i]:
                    a+=1
                else:
                    b+=1
            for j in range(i+1,len(r)):
                if r[j]>r[i]:
                    c+=1
                else:
                    d+=1
            s+=a*c+b*d
        return s


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(0, len(rating)):
            for j in range(i + 1, len(rating)):
                for k in range(j + 1, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        count += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        count += 1
        return count
        


class Solution:
    def numTeams(self, rating: List[int]) -> int: 
        
        # can use DP to speed up 
        
        # iteraton methods
        res = 0
        for com in combinations(rating, 3): 
            if com[0] > com[1] > com[2] or com[0] < com[1] < com[2]: 
                res += 1 
                
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        l=len(rating)
        ans=0
        for i in range(l):
            for j in range(i, l):
                for k in range(j, l):
                    if rating[i]<rating[j]<rating[k]:
                        ans+=1
                    if rating[i]>rating[j]>rating[k]:
                        ans+=1
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        r = 0
        for i in range(n):
            for j in range(i,n):
                for k in range(j,n):
                    if rating[i] < rating[j] < rating[k]:
                        r += 1
                    if rating[i] > rating[j] > rating[k]:
                        r += 1
        return r

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        for com in combinations(rating, 3): 
            if com[0] > com[1] > com[2] or com[0] < com[1] < com[2]: 
                res += 1 
                
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans=0
        for i in range(len(rating)):
            for j in range(i,len(rating)):
                for k in range(j,len(rating)):
                    if (rating[i]<rating[j] and rating[j]<rating[k]) or (rating[i]>rating[j] and rating[j]>rating[k]):ans+=1
        return ans


class Solution:
    def numTeams(self, r: List[int]) -> int:
        # we can do this in brute force with n^3
        
        # trivially impossible if fewer than 3 soldiers
        if len(r) < 3:
            return 0
        
        teams = 0
        
        # brute force
        
        for i in range(0, len(r) - 2):
            for j in range(i + 1, len(r) - 1):
                if i >= j:
                    break
                for k in range(j + 1, len(r)):
                    if j >= k:
                        break
                        
                    if r[i] < r[j] < r[k] or r[i] > r[j] > r[k]:
                        teams += 1
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        #print((rating[i], rating[j],rating[k]))
                        count += 1
                        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j + 1, len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        count+=1
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        l = [0]*len(rating)
        m = [0]*len(rating)
        for p,q in enumerate(rating):
            for j in range(p):
                if rating[j] < q:
                    l[p] += 1
                    res += l[j]
                else:
                    m[p] += 1
                    res += m[j]
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        g, s = [0] * n, [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                print((rating[j]))
                if rating[j] > rating[i]:
                    g[i] += 1
                else:
                    s[i] += 1
        print(g)
        print(s)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                if rating[j] > rating[i]:
                    ans += g[j]
                else:
                    ans += s[j]
        
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            l = [rating[i]]
            for j in range(i+1,len(rating)):
                l.append(rating[j])
                for k in range(j+1,len(rating)):
                    if (l[0] > l[1] and l[1] > rating[k]) or (l[0] < l[1] and l[1] < rating[k]):
                        count += 1
                l = l[:1]
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n, cnt = len(rating), 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    cnt += (rating[i] > rating[j] > rating[k]) or (rating[i] < rating[j] < rating[k])
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # brute force
        length = len(rating)
        ans = []

        for i in range(length-2):
            temp = rating[i]

            for j in range(i+1, length):
                if rating[j] > temp:
                    for k in range(j+1, length):
                        if rating[k] > rating[j]:
                            ans.append([rating[i], rating[j], rating[k]])

                if rating[j] < temp:
                    for k in range(j+1, length):
                        if rating[k] < rating[j]:
                            ans.append([rating[i], rating[j], rating[k]])

        return len(ans)


import itertools

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # mycom = [c for c in itertools.combinations(rating, 3)]
        ans = 0
        for item in itertools.combinations(rating, 3):
            if item[0] < item[1] and item[1] < item[2]:
                ans += 1
            if item[0] > item[1] and item[1] > item[2]:
                ans += 1
        return ans


class Solution:
    def numTeams(self, ratings: List[int]) -> int:
        n = len(ratings)
        count = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                    if ratings[i] < ratings[j] < ratings[k]:
                        count += 1
                    if ratings[i] > ratings[j] > ratings[k]:
                        count += 1
                        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(0, len(rating)):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        count += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        count += 1
        return count
        


class Solution:
    def numTeams(self, nums: List[int]) -> int:
        n=len(nums)
        res = 0
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    res+= 1 if (nums[i]<nums[j] and nums[j]<nums[k]) or (nums[i]>nums[j] and nums[j]>nums[k]) else 0
        return res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n=len(rating)
        count=0
        for i in range(0,n):
                for j in range(i+1,n):
                        for k in range(j+1,n):
                                if rating[i]>rating[j] and rating[j]>rating[k]:
                                        count+=1
                                elif rating[i]<rating[j] and rating[j]<rating[k] :
                                        count+=1
        return count
                
                        
                


# Version B:  O(n^2) solution with (primitive) nested loops for building our 4 counting variables.
class Solution:
    def numTeams(self, A) -> int:
        L = len(A)
        result = 0
        for j in range(1,L-1):
            x, loL, loR, hiL, hiR = A[j], 0, 0, 0, 0
            for i in range(j):
                if A[i]<x:

                    print('x',x)
                    print('A[i]',A[i])
                    loL += 1
                else:
                    hiL += 1
            for k in range(j+1,L):
                if A[k]<x:
                    loR += 1
                else:
                    hiR += 1
            result += loL*hiR + hiL*loR
            print('resut',result)
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                if rating[i] > rating[j] or rating[i] < rating[j]:
                    for k in range(j+1,len(rating)):
                        if rating[i] > rating[j] and rating[j] > rating[k]:
                            cnt += 1
                        elif rating[i] < rating[j] and rating[j] < rating[k]:
                            cnt += 1
        return cnt


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if((rating[i]<rating[j]<rating[k] and i < j < k) or (rating[i]>rating[j]>rating[k] and i<j<k)):
                        count+=1
        return count

class Solution:
    def numTeams(self, a: List[int]) -> int:
        count=0
        for i in range(len(a)-2):
            for j in range(i+1,len(a)-1):
                for k in range(j+1,len(a)):
                    if a[i]<a[j]<a[k]:
                        count+=1
                    if a[i]>a[j]>a[k]:
                        count+=1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        n = len(rating)
        team_sum = 0
        teams = []
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    if rating[i] < rating[j] < rating[k]:
                        team_sum += 1
                    if rating[i] > rating[j] > rating[k]:
                        team_sum += 1
                        
        return team_sum

class Solution:
    def numTeams(self, nums: List[int]) -> int:
        n=len(nums)
        return sum([1 if (nums[i]<nums[j] and nums[j]<nums[k]) or (nums[i]>nums[j] and nums[j]>nums[k]) else 0 for i in range(n) for j in range(i+1,n) for k in range(j+1,n)])


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0 
        n= len(rating)
        for i in range(n-2):
            for j in range(i+1,n-1):
                for k in range(j+1,n):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        count +=1
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # just use i,j,k three pointers. then it is O^3
        # brute-force O^3 solution would be to use three index pointers
        # spacewise, this would be just O(1)
        
        count = 0
        
        for i in range(0, len(rating)-2):
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if ((rating[i] < rating[j]) and (rating[j] < rating[k])) or ((rating[i] > rating[j]) and (rating[j] > rating[k])):
                        count += 1
                    
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # just use i,j,k three pointers. then it is O^3
        # brute-force O^3 solution would be to use three index pointers
        # spacewise, this would be just O(1)
        
        count = 0
        
        for i in range(0, len(rating)-2):
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if ((rating[i] < rating[j]) and (rating[j] < rating[k])) or ((rating[i] > rating[j]) and (rating[j] > rating[k])):
                        count += 1
                    
        return count
        


class Solution:
    def numTeams(self, rat: List[int]) -> int:
        if(len(rat)<3):
            return 0
        else:
            c=0
            for i in range(len(rat)):
                for j in range(i+1,len(rat)):
                    for k in range(j+1,len(rat)):
                        if(rat[i]>rat[j]>rat[k]):
                            c+=1
            rat.reverse()                
            for i in range(len(rat)):
                for j in range(i+1,len(rat)):
                    for k in range(j+1,len(rat)):
                        if(rat[i]>rat[j]>rat[k]):
                            c+=1                
            return c                

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            less_left = 0
            less_right = 0
            greater_left = 0
            greater_right = 0
            
            for j in range(len(rating)):
                if j < i:
                    if rating[i] > rating[j]:
                        less_left += 1
                    elif rating[i] < rating[j]:
                        greater_left += 1
                elif j > i:
                    if rating[i] > rating[j]:
                        less_right += 1
                    elif rating[i] < rating[j]:
                        greater_right += 1
            count += less_left * greater_right + greater_left * less_right
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for idx0 in range(len(rating)-2):
            for idx1 in range(idx0+1, len(rating)-1):
                for idx2 in range(idx1+1, len(rating)):
                    #print(idx0,idx1,idx2)
                    if rating[idx0]<rating[idx1] and rating[idx1] < rating[idx2]:
                        count+=1
                    elif rating[idx0]>rating[idx1] and rating[idx1] > rating[idx2]:
                        count+=1
        return count
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        cnt += 1
                    elif rating[i] < rating[j] and rating[j] < rating[k]:
                        cnt += 1
        return cnt


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c=0
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if i<j<k:
                        if rating[i]>rating[j]>rating[k] or rating[i]<rating[j]<rating[k]:
                            c+=1
        return c


from itertools import combinations
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        valid = 0
        for i in combinations(rating, 3):
            if (i[0] < i[1]):
                if (i[1] < i[2]):
                    valid += 1
            elif (i[0] > i[1]):
                if (i[1] > i[2]):
                    valid += 1
        return valid


from itertools import combinations
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        valid = 0
        for i in combinations(rating, 3):
            if (i[0] < i[1] < i[2]) or (i[0] > i[1] > i[2]):
                valid += 1
        return valid


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        for i in range(len(rating)):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    if((rating[i]>rating[j] and rating[j]>rating[k]) or (rating[i]<rating[j] and rating[j]<rating[k])):
                        teams+=1
        return teams


from itertools import combinations

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        for tupl in combinations(rating, 3):
            if (tupl[0] < tupl[1] < tupl[2]) or (tupl[0] > tupl[1] > tupl[2]):
                result += 1
        return result


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3: 
            return 0
        
        ans = 0
        
        for i in range(0, len(rating)-2):
            for j in range(i + 1, len(rating) - 1):
                for k in range(j + 1, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        ans += 1
                    elif rating[i] > rating[j] and rating[j] > rating[k]:
                        ans += 1 
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(0, len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if rating[i]< rating[j] and rating[j] < rating[k]:
                        count+=1 
                    elif rating[i]> rating[j] and rating[j]>rating[k]:
                        count+=1
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        out = 0
        for i in range(1,n-1):
            lless = lgreat = rless = rgreat = 0
            for j in range(i-1,-1,-1):
                if rating[j]>rating[i]:
                    lgreat+=1
                if rating[j]<rating[i]:
                    lless+=1
            for j in range(i+1,n):
                if rating[j]>rating[i]:
                    rgreat+=1
                if rating[j]<rating[i]:
                    rless+=1              
            out += (lless*rgreat)+(lgreat*rless)
        return out

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n= len(rating)
        count  = 0
        for i in range(n-2):
            for j in range(i+1,n-1):
                for k in range(j+1,n):
                    if (rating[i]>rating[j]>rating[k]) or (rating[i]<rating[j]<rating[k]):
                        count += 1
                    else:
                        k += 1
        return count


from itertools import combinations

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return len([(x, y, z) for x, y, z in list(combinations(rating, 3)) if (x < y and y < z) or (x > y and y > z)])

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n=len(rating)
        c=0
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    if rating[i]<rating[j] and rating[j]<rating[k]:
                        c+=1
                    if rating[i]>rating[j] and rating[j]>rating[k]:
                        c+=1
        return c

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for id_i, i in enumerate(rating):
            for id_j, j in enumerate(rating[id_i:]):
                id_ij = id_i + id_j
                for id_k, k in enumerate(rating[id_ij:]):
                    id_ijk = id_ij + id_k
                    if 0<=i and id_i < id_ij and id_ij < id_ijk:
                        if i < j and j < k:
                            count += 1
                        if i > j and j > k:
                            count += 1
        return count

class Solution:
    def numTeams(self, a: List[int]) -> int:
        list1=[]
        for i in range(len(a)-2):
            for j in range(i+1,len(a)-1):
                for k in range(j+1,len(a)):
                    if a[i]<a[j]<a[k]:
                        list1.append((1))
                    if a[i]>a[j]>a[k]:
                        list1.append((1))
        return len(list1)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        n = len(rating)
        for i in range(0,n-2):
            for j in range(i+2,n):
                for k in range(i+1,j):
                    if rating[k] > rating[i] and rating[k] < rating[j]:
                        result += 1
                    elif rating[k] < rating[i] and rating[k] > rating[j]:
                        result += 1
                        
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0

        teamsCount = 0

        for i in range(len(rating) - 2):
            for j in range(i + 1, len(rating) - 1):
                for k in range(j + 1, len(rating)):
                    if (
                        (rating[i] > rating[j] > rating[k])
                        or (rating[i] < rating[j] < rating[k])
                    ):
                        teamsCount += 1
        
        return teamsCount

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c=0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if rating[i]<rating[j] and rating[j]<rating[k]:
                        c+=1
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if rating[i]>rating[j] and rating[j]>rating[k]:
                        c+=1
        return c


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        l = len(rating)
        count = 0
        
        for i in range(0,l-2):
            for j in range(i+1,l-1):
                for k in range(j+1,l):
                    if rating[i] > rating[j] and rating[j]>rating[k]:
                        count += 1
                    if rating[i] < rating[j] and rating[j]<rating[k]:
                        count += 1
        return count
                    
                        
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        i = 0
        j = 0
        k = 0
        numOfTeams = 0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        numOfTeams += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        numOfTeams += 1
        return numOfTeams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        greater = defaultdict(int)
        less = defaultdict(int)
        ans = 0
  
        for i in range(len(rating)-1):
            for j in range(i+1, len(rating)):
                if rating[j] > rating[i]:
                    greater[i] += 1
                else:
                    less[i] += 1
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)):
                if rating[i] < rating[j]:
                    ans += greater[j]
                else:
                    ans += less[j]
        
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        unique = []
        
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        unique.append((rating[i], rating[j], rating[k]))
                        
        
        return len(unique)

class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        
        return self.increaser(rating,0,0)+ self.decreaser(rating,0,pow(10,5)+1)
    
    
    def increaser(self,rating,num, last):
        
        if num==3:
            return 1
        
        if len(rating)==0:
            return 0
        
        count=0
        for i in range(len(rating)):
            
            if rating[i]>last:
                count+=self.increaser(rating[i+1:],num+1,rating[i])
                
        return count
    
    def decreaser(self,rating,num, last):
        
        if num==3:
            return 1
        
        if len(rating)==0:
            return 0
        
        count=0
        for i in range(len(rating)):
            
            if rating[i]<last:
                count+=self.decreaser(rating[i+1:],num+1,rating[i])
                
        return count
    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        counts = 0
        
        for ix in range(len(rating) - 2):
            for iy in range(ix, len(rating) - 1):
                for iz in range(iy, len(rating)):
                    if rating[ix] < rating[iy] and rating[iy] < rating[iz]:
                        counts += 1
                    elif rating[ix] > rating[iy] and rating[iy] > rating[iz]:
                        counts += 1
        return counts

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i + 1):
                for k in range(j + 1):
                    if rating[i] < rating[j] < rating[k]:
                        count += 1
                    
                    if rating[i] > rating[j] > rating[k]:
                        count += 1
        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        #Brute Force.
        teams = 0
        for i in range(0, len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    
                    if (i<j<k) and(rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) :
                        teams += 1
        
        return teams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        for i in range(len(rating)-2):
            for j in range(i + 1,len(rating)-1):
                for k in range(j + 1,len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        ans += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        ans += 1
            
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        
        n = len(rating)
        for i in range(n):
            for j in range(i, n):
                for k in range(j, n):
                    if rating[i]<rating[j] and rating[j] <rating[k]:
                        ans+=1
        rating.reverse()
        for i in range(n):
            for j in range(i, n):
                for k in range(j, n):
                    if rating[i]<rating[j] and rating[j] <rating[k]:
                        ans+=1
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if rating[i]<rating[j] and rating[j]<rating[k]:
                        count+=1
                    if rating[i]>rating[j] and rating[j]>rating[k]:
                        count+=1
                        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans=0
        
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1,1):
                for k in range(j+1,len(rating),1):
                    if (rating[i]<rating[j]) and (rating[j]<rating[k]):
                        ans+=1
                    if (rating[i]>rating[j]) and (rating[j]>rating[k]):
                        ans+=1
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        lenn = len(rating)
        for mid in range(1,lenn-1):
            left_less,right_more = 0,0
            left_more,right_less = 0,0
            
            for j in range(mid):
                if rating[j]<rating[mid]:
                    left_less+=1
                elif rating[j]>rating[mid]:
                    left_more+=1
                    
            for j in range(mid+1,lenn):
                if rating[j]<rating[mid]:
                    right_less+=1
                elif rating[j]>rating[mid]:
                    right_more+=1
        
            res += (left_less*right_more)+(left_more*right_less)
        return res
        
        #Brute Force
        # lenn = len(rating)
        # res = 0
        # for i in range(lenn):
        #     for j in range(i+1,lenn):
        #         for k in range(j+1,lenn):
        #             if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
        #                 res+=1
        # return res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) <= 2: 
            return 0
        n = len(rating)
        cnt = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        cnt += 1
        
        return cnt
    
    def numTeams1(self, rating: List[int]) -> int:
        pass


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        if n < 3:
            return 0
        return sum(rating[i] < rating[j] < rating[k]
                   or rating[i] > rating[j] > rating[k]
                   for i in range(n-2)
                   for j in range(i+1, n-1)
                   for k in range(j+1, n))

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if (rating[i] < rating[j] and rating[j] < rating[k]) or (rating[i] > rating[j] and rating[j] > rating[k]):
                        count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # brute force attempt
        n = len(rating)
        ans = 0
        
        for i in range(n):
            for j in range(i, n):
                for k in range(j, n):
                    
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        ans += 1
                    
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        ans += 1
        return ans

class Solution:
    def numTeams(self, a: List[int]) -> int:
        greater,lesser=0,0
        c=0
        n=len(a)
        for i in range(0,n):
            for j in range(i+1,n):
                if(a[i]<a[j]):
                    greater=0
                    lesser=1
                elif(a[i]>a[j]):
                    lesser=0
                    greater=1
                else:
                    continue
                for k in range(j+1,n):
                    if(a[j]<a[k] and lesser==1):
                        c=c+1
                    elif(a[j]>a[k] and greater==1):
                        c=c+1
        return c


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        count = 0
        
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        count += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        count += 1
        return count
    


from math import comb
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        sum = 0
        for i in range(len(rating) -2):
            for j in range(i, len(rating) - 1):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        sum += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        sum += 1
        return sum


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0 
        for i in range(0,len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        res += 1
        return res

class Solution:
    
    def three(self,three,final):
        
        if three==True:
            print(final)
            
            
    def numTeams(self, rating: List[int]) -> int:
        
        i=0
        j=0
        k=0
        
        final=[]
        
        three=None
        count=0
        while i<len(rating):  #2,5,7
            j=i+1
            while j < len(rating):
                k=j+1
                while k < len(rating):
                    if (rating[i] < rating[j] < rating[k]) or  (rating[i] > rating[j] > rating[k]):
                        count += 1
                    k+=1
                j+=1
            i+=1
        return count
                    
        
    
    def numTeams_praj(self, rating: List[int]) -> int:
        
        i=0
        final=[]
        
        three=None
        count=0
        while i<len(rating):  #2,5,7
            final.append(rating[i])#2
            j=i+1
            while j<len(rating):
                final.append(rating[j])
                if rating[j]>rating[i]:
                    new=rating[j+1:]
                    for ele in new:
                        if ele>rating[j]:
                            final.append(ele)
                            three=True
                            
                            self.three(three,final)
                            count+=1
                            final=[]
                            final.append(rating[i])
                            final.append(rating[j])
                            
                        else:
                            three=False
                            rating[j]=ele
            
                    
                 
             
                j+=1
            i+=1
        return count
        
        

                        
                        
                     
               
                
                
          
          
        
        
            


from itertools import cycle, islice
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        # solution 1
        count = 0
        for id_i, i in enumerate(rating):
            for id_j, j in enumerate(rating[id_i:]):
                id_ij = id_i + id_j
                for id_k, k in enumerate(rating[id_ij:]):
                    id_ijk = id_ij + id_k
                    if 0<=i:
                        if i < j and j < k:
                            count += 1
                        if i > j and j > k:
                            count += 1
        return count
    
    
        # solution 2 - itertools-islice
        # count = 0
        # print(list(islice(rating, 0)))
        # return count
    
        # solution 3 - numpy
        # count = 0
        # arr = rating
        # for i in range(arr.shape[0]):
        #     ij = i+j
        #     for j in range(arr[i:]):
        #         for k in range(arr[ij:]):
        #             ijk = ij + k
        #             if arr[i] > 0
            
        #return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        
        if n < 3:
            return 0
        
        greater = [0] * n
        smaller = [0] * n
        for i in range(len(rating)-1):
            for j in range(i+1, len(rating), 1):
                if rating[j] > rating[i]:
                    greater[j] += 1
                elif rating[j] < rating[i]:
                    smaller[j] += 1

        total = 0
        for j in range(1, len(rating), 1):
            for k in range(j+1, len(rating), 1):
                if rating[k] > rating[j]:
                    total += greater[j]
                elif rating[k] < rating[j]:
                    total += smaller[j]

        return total

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        if n < 3:
            return 0
        return sum((rating[j] - rating[i]) * (rating[k] - rating[j]) > 0
                   for i in range(n-2)
                   for j in range(i+1, n-1)
                   for k in range(j+1, n))

class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        @lru_cache(maxsize = None)
        def check(a,b):
            if rating[a]>rating[b]:
                return 1
            elif rating[a]<rating[b]:
                return 2
            else:
                return 0
        for ind,val in enumerate(rating[2:]):
            ind+=2
            for a in range(ind-1):
                for b in range(a+1,ind):
                    c = check(a,b)
                    if c == 1 and val < rating[b] or c==2 and val > rating[b]:
                        res +=1
        return res


class Solution:
    def my_function(self, start: int, end: int) -> int:
        if end - start <= 1:
            return 0
        s = sorted(range(end-start), key=lambda x: self.rating[start + x])
        return abs(s.index(0) - s.index(end-start-1)) - 1
        
    def numTeams(self, rating: List[int]) -> int:
        self.rating = rating
        total = 0
        l = len(rating)
        for i in range(l):
            for j in range(l-i-1):
                a = self.my_function(i, l-j)
                total += a
                
        return total

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        #find all ascending and descending combos in order of length three
        #o(n^3) solution
        count = 0
        i = 0
        while i < len(rating):
            j = i + 1
            while j < len(rating):
                k = j + 1
                while k < len(rating):
                    if (rating[i] > rating[j] > rating[k]) or (rating[i] < rating[j] < rating[k]):
                        count += 1
                    k += 1
                j += 1
            i += 1
        return count
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        def isValid(a,b,c):
            return (a < b < c) or (a > b > c)
        
        count = 0
        for i in range(len(rating)-2):
            for j in range(i, len(rating)-1):
                for k in range(j, len(rating)):
                    if isValid(rating[i], rating[j], rating[k]):
                        count += 1
        return count
                        
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        comb = list(itertools.combinations(rating, r=3))
        
        ans = 0
        for tup in comb:
            if tup[0] < tup[1] < tup[2] or tup[0] > tup[1] > tup[2]:
                ans+=1
                
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        from itertools import combinations
        com = list(combinations(rating,3))

        cnt = 0
        if len(rating) < 2:
          return 0
        for t in com:
          if t[0] > t[1] > t[2] or t[0] < t[1] < t[2]:
            cnt += 1
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        i=0
        final=[]
        add=0
        while i<len(rating):
            
            j=len(rating)-1
            while j>i+1:
                # print(rating[i],rating[j])
                k=j-1
                while k>i:
                    # print(rating[i],rating[k],rating[j])
                    if rating[i]<rating[k] and rating[k]<rating[j]:
                        add+=1
                    if rating[i]>rating[k] and rating[k]>rating[j]:
                        add+=1
                    k-=1
            
                j-=1
            i+=1
        return add
#             j=i+1
#             k=len(rating)-1
            
#             while j<k:
#                 print(rating[i],rating[j],rating[k])
                
#                 if rating[i]<rating[j] and rating[j]<rating[k]:
#                     final.append((rating[i],rating[j],rating[k]))
                    
#                 elif rating[i]>rating[j] and rating[j]>rating[k]:
#                     final.append((rating[i],rating[j],rating[k]))
                
#                 j+=1
                
#                 print(rating[i],rating[j],rating[k])
#                 print()
#             i+=1
#         print(final)


from itertools import combinations
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = list(combinations(rating,3))
        count = 0
        for i in res :
            if i[0] > i[1] > i[2] or i[0] < i[1] < i[2] :
                count +=1
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        if len(rating) < 3:
            return 0
        
        from functools import lru_cache
        @lru_cache(maxsize = None)
        def bt(start, lastVal, countAdded, sign):
            if countAdded == 3:
                return 1
            
            if start == len(rating):
                return 0
            
            totalCount = 0
            for i in range(start, len(rating)):
                if lastVal*sign < rating[i]*sign:
                    totalCount += bt(i + 1, rating[i], countAdded + 1, sign)
            return totalCount
        
        return bt(0, 0, 0, 1) + bt(0, float('inf'), 0, -1)


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        i = 0
        j = 1
        k = 2
        count = 0
        while i < len(rating)-2:
            while j < len(rating)-1:
                while k < len(rating):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        count += 1
                    k += 1
                j += 1
                k = j + 1
            i += 1
            j = i + 1
            k = i + 2
        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        track = []
        res = 0
        def backtrack(increase, index):
            nonlocal res
            if len(track) == 3:
                
                res +=1
                return
            for i in range(index, len(rating)):
                if index == 0:
                    track.append(rating[i])
                    backtrack(increase, i+1)
                    track.pop()
                else:
                    if increase:
                        if rating[i] > track[-1]:
                            track.append(rating[i])
                            backtrack(True, i+1)
                            track.pop()
                    if not increase:
                        if rating[i] < track[-1]:
                            track.append(rating[i])
                            backtrack(False, i+1)
                            track.pop()
        backtrack(True, 0)
        backtrack(False, 0)
        return res


class Solution:
    
    def checkList(self, head: List[List[int]], tail: List[int], init: int) -> int:
        result = init
        head_copy = head[:]
        num = tail[0]
        
        for i in head_copy:
            if len(i) == 2:
                if (i[0] < i[1] and i[1] < num) or (i[0] > i[1] and i[1] > num):
                    result+=1   
            else:
                head.append(i + [num])    

        if len(tail) == 1: 
            return result
        else:
            return self.checkList(head, tail[1:], result)
        
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3: 
           return 0 
        return self.checkList([[],[rating[0]]], rating[1:], 0)   

class Solution:
    
    def checkList(self, head: List[List[int]], tail: List[int], init: int) -> int:
        result = init
        head_copy = list(head)
        num = tail[0]
        
        for i in head_copy:
            if len(i) == 2:
                if (i[0] < i[1] and i[1] < num) or (i[0] > i[1] and i[1] > num):
                    result+=1   
            else:
                head.append(i + [num])    

        if len(tail) == 1: 
            return result
        else:
            return self.checkList(head, tail[1:], result)
        
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3: 
           return 0 
        return self.checkList([[],[rating[0]]], rating[1:], 0)   

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return sum( 1 for k in range(len(rating)) for j in range(k) for i in range(j) if (rating[i]<rating[j]<rating[k]) or (rating[i]>rating[j]>rating[k]))
    
       
                    
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                k = j+1
                while(k<len(rating)):
                    if (rating[k]>rating[j]) and (rating[j]>rating[i]):
                        count = count+1
                    elif(rating[k]<rating[j]) and (rating[j]<rating[i]):
                        count = count+1
                    k = k+1
            
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        i = 0
        j = 1
        k = 2
        count = 0
        while i < len(rating)-2:
            while j < len(rating)-1:
                while k < len(rating):
                    if rating[i] < rating[j] < rating[k]:
                        count += 1
                    elif rating[i] > rating[j] > rating[k]:
                        count += 1
                    k += 1
                j += 1
                k = j + 1
            i += 1
            j = i + 1
            k = i + 2
        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        else:
            res = 0
            for i in range(len(rating)-2):
                for j in range(i, len(rating)-1):
                    for k in range(j, len(rating)):
                        if(rating[i]>rating[j] and rating[j]>rating[k]):
                            res += 1
                        elif(rating[i]<rating[j] and rating[j]<rating[k]):
                            res += 1
            return res
                            
                


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        table = [[1 if rating[i] > rating[j]  else 0  for j in range(i+1,len(rating))] for i in range(0,len(rating)-1)]
        table = table + [[]]
        count = 0
        
        for i in range(0,len(table)):
            for j in range(0,len(table[i])):
                if table[i][j] == 1:
                    count += sum(table[i+1+j])
                else:
                    count += (len(table[i+1+j])-sum(table[i+1+j]))
                    
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if (rating[i] > rating[j] and rating[j] > rating[k]) or (rating[i] < rating[j] and rating[j] < rating[k]):
                        count += 1
        return count

class Solution:
    def numTeams(self, a: List[int]) -> int:
        output = 0
        for i in range(len(a[:-2])):
            for j in range(len(a[:-1])):
                if a[j]>a[i] and j>i:
                    for k in range(len(a)):
                        if a[k]>a[j] and k>j:
                            output +=1
                elif a[j]<a[i] and j>i:
                    for k in range(len(a)):
                        if a[k]<a[j] and k>j:
                            output +=1
        return output


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        result+=1
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
      res = []
      for i in range(len(rating)):
        for j in range(i, len(rating)):
          for k in range(j, len(rating)):
            if(rating[i] > rating[j] and rating[j] > rating[k]):
              res.append((rating[i], rating[j], rating[k]))
            if(rating[i] < rating[j] and rating[j] < rating[k]):
              res.append((rating[i], rating[j], rating[k]))
      return len(res)


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            l = [rating[i]]
            for j in range(i+1,len(rating)):
                l.append(rating[j])
                for k in range(j+1,len(rating)):
                    if (l[0] > l[1] and l[1] > rating[k]) or (l[0] < l[1] and l[1] < rating[k]):
                        count += 1
                    
                l = l[:1]
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        
        n = len(rating)
        
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        count += 1
        
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        ratings = rating
        for i in range(len(ratings)):
            for j in range(i + 1, len(ratings)):
                for k in range(j + 1, len(ratings)):
                    if ratings[i] > ratings[j] > ratings[k]:
                        count += 1
                    elif ratings[i] < ratings[j] < ratings[k]:
                        count += 1
        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        combs = combinations(rating,3)
        return sum((c[0] < c[1] < c[2]) or (c[0] > c[1] > c[2]) for c in combs)
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        a = rating
        n = len(a)
        ans = 0
        for i in range(n):
            left = [0, 0]
            for j in range(i):
                if a[j] < a[i]:
                    left[0] += 1
                elif a[j] > a[i]:
                    left[1] += 1
            right = [0, 0]
            for j in range(i + 1, n):
                if a[j] < a[i]:
                    right[0] += 1
                elif a[j] > a[i]:
                    right[1] += 1
            ans += left[0] * right[1] + left[1] * right[0]
        return ans

class Solution:
    def numTeams(self, r: List[int]) -> int:
        c=0
        for i in range(len(r)-2):
            for j in range(i+1,len(r)-1):
                for k in range(j+1,len(r)):
                    if(r[i]>r[j]>r[k]) or (r[i]<r[j]<r[k]):
                        c+=1
        return c
                        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i,len(rating)):
                for k in range(j,len(rating)):
                    if rating[i]<rating[j]<rating[k]:
                        count += 1
                    if rating[i]>rating[j]>rating[k]:
                        count += 1
        return count


from itertools import combinations

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return len([comb for comb in list(combinations(rating, 3)) if (comb[0]<comb[1] and comb[1]<comb[2]) or (comb[0]>comb[1] and comb[1]>comb[2])])

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        out = []
        
        if n<3:
            return 0
        
        for i in range(n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                    #print(rating[i],rating[j],rating[k])
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        out.append([i,j,k])
        #print(out)
        return len(out)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        count = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                     if rating[i] > rating[j] > rating[k] or rating[i] < rating[j] < rating[k]:
                            count += 1
                            
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        
        
        teams: Set[Tuple[int, int, int]] = set()
        for i, s1 in enumerate(rating):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    s2 = rating[j]
                    s3 = rating[k]
                    if s1 > s2 > s3 or s1 < s2 < s3:
                        teams.add((s1, s2, s3))
        
        return len(teams)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        N = len(rating)
        for i in range(N):
            for j in range(i + 1, N):
                for k in range(j + 1, N):
                    ans += int(rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k])
        
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        teams_count = 0
        
        i = 0
        
        while i < len(rating)-2:
            j = i+1
            while j < len(rating) -1:
                k = j+1
                while k < len(rating):
                    if ((rating[i] < rating[j]) and (rating[j] < rating[k])) or ((rating[k] < rating[j]) and (rating[j] < rating[i])):
                        teams_count +=1
                 
                    k+=1
                j+=1
            i+= 1
            
        return teams_count
            
                    
                
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        def get_triplets(r):
            res = 0
            for i in range(n):
                for j in range(i + 1, n):
                    for k in range(j + 1, n):
                        res += 1 if (r[i] < r[j] < r[k]) else 0
            return res

        return get_triplets(rating) + get_triplets(rating[::-1])

# class Solution:
#     def numTeams(self, rating: List[int]) -> int:
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        asc = dsc = 0
        for i,v in enumerate(rating):
            llc = rgc = lgc = rlc =0
            for l in rating[:i]:
                if l < v:
                    llc += 1
                if l > v:
                    lgc += 1
            for r in rating[i+1:]:
                if r > v:
                    rgc += 1
                if r < v:
                    rlc += 1
            asc += llc * rgc
            dsc += lgc * rlc            
        return asc + dsc

class Solution:
    def numTeams(self, rating: List[int]) -> int:
      N = len(rating)
      numteams = 0
      
      # strictly increasing
      for i in range(N):
        left = 0
        right = 0
        
        for j in range(N):
          if(j < i):
            if(rating[j] < rating[i]):
              left += 1
          elif(j > i):
            if(rating[i] < rating[j]):
              right += 1
        numteams += (left*right)
        
      # strictly decreasing
      for i in range(N):
        left = 0
        right = 0
        
        for j in range(N):
          if(j < i):
            if(rating[i] < rating[j]):
              left += 1
          elif(j > i):
            if(rating[i] > rating[j]):
              right += 1
        numteams += (left*right)
    
      return numteams
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        lens=len(rating)
        count=0
        for i in range(lens-1):
            for j in range(i+1,lens-1):
                for k in range(j+1,lens):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        count+=1
                    
                
        return count

from itertools import combinations

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) in rating and len(rating) == 3:
            return 0
        else:
            output = list(combinations(rating,3))
            count = len(output)
            for i in output:
                if i[0]<i[1] and i[1]>i[2]:
                    count -= 1
                elif i[0]>i[1] and i[1]<i[2]:
                    count -= 1
            return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        teams = []
        
        for i in range(0, len(rating)): 
            
            for j in range(i + 1, len(rating)):
    
                for k in range(j + 1, len(rating)):
            
                    if (rating[i] < rating[j] and rating[j] < rating[k]) or (rating[i] > rating[j] and rating[j] > rating[k]):
                    
                        teams.append([i, j, k])
        
        return len(teams)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        l = len(rating)
        count = 0
        
        for i in range(l - 2):
            for j in range(i + 1, l-1):
                for k in range(j + 1, l):
                    if rating[k] > rating[j] > rating[i] or rating[k] < rating[j] < rating[i]:
                        count += 1
                        
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        for i in range(len(rating)-2):
            for j in range(i, len(rating)-1):
                for k in range(j, len(rating)):
                    if rating[i] > rating[j] > rating[k]:
                        result += 1
                    if rating[i] < rating[j] < rating[k]:
                        result += 1
        return result
                    
                    
                    
#         up_list = []
#         down_list = []
#         result = 0
#         for i in range(len(rating)):
#             up_list.append([i])
#             down_list.append([i])
#             for sub_list in up_list:
#                 if len(sub_list) == 1 and sub_list[0] < rating[i]:
#                     new_list = sub_list + [rating[i]]
#                     up_list.append(new_list)
#                 elif len(sub_list) == 2 and sub_list[-1] < rating[i]:
#                     up_list.append([sub_list[0], rating[i]])
#                     up_list.append([sub_list[1], rating[i]])
#                     result += 1
#                 elif len(sub_list) == 2 and sub_list[0] < rating[i]:
#                     up_list.append([sub_list[0], rating[i]])
#                     up_list.append([rating[i], sub_list[1]])
            
#             for sub_list in down_list:
#                 if len(down_list) == 1 and down_list[0] > rating[i]:
#                     new_list = sub_list + [rating[i]]
#                     down_list.append(new_list)
#                 elif len(sub_list) == 2 and sub_list[-1] > rating[i]:
#                     down_list.append([sub_list[0], rating[i]])
#                     down_list.append([sub_list[1], rating[i]])
#                     result += 1
#                 elif len(sub_list) == 2 and sub_list[0] > rating[i]:
#                     down_list.append([sub_list[0], rating[i]])
#                     down_list.append([rating[i], sub_list[1]])
#         return result
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = []
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1,len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        teams.append([i,j,k])
        return len(teams)

class Solution:
    def canFormATeam(self, r1: int, r2: int, r3: int) -> bool:
        return (r1 < r2 < r3) or (r1 > r2 > r3)


    def numTeams(self, rating: List[int]) -> int:
        n_teams: int = 0

        for i in range(len(rating) - 2):
            for j in range(i + 1, len(rating) - 1):
                for k in range(j + 1, len(rating)):
                    if self.canFormATeam(rating[i], rating[j], rating[k]):
                        n_teams += 1
                        
        return n_teams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        answer = 0
        n = len(rating)

        for i in range(n):
            for j in range(n):
                if j < i:
                    continue
                for k in range(n):
                    if j < k:
                        if rating[i] < rating[j] < rating[k]:
                            answer += 1
                        elif rating[i] > rating[j] > rating[k]:
                            answer += 1

        return answer

class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        arr = []
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        arr.append([rating[i] , rating[j] , rating[k]])
        if arr:
            return len(arr)
        return 0
                    
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = range(1, len(rating) + 1)
        teams = list(zip(teams, rating))
        teams_inc = sorted(teams, key=lambda x: x[1])
        teams_dec = sorted(teams, key=lambda x: -x[1])
        ans = 0
        for i in range(0, len(teams) - 2):
            for j in range(i + 1, len(teams) - 1):
                for k in range(j + 1, len(teams)):
                    if teams_inc[i][0] < teams_inc[j][0] < teams_inc[k][0]:
                        ans += 1
        for i in range(0, len(teams) - 2):
            for j in range(i + 1, len(teams) - 1):
                for k in range(j + 1, len(teams)):
                    if teams_dec[i][0] < teams_dec[j][0] < teams_dec[k][0]:
                        ans += 1
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        less_r = [0] * n
        bigger_r = [0] * n
        less_l = [0] * n
        bigger_l = [0] * n
        for i in range(n):
            for j in range(i):
                less_l[i] += rating[i] > rating[j]
                bigger_l[i] += rating[i] < rating[j]
            for j in range(i + 1, n):
                less_r[i] += rating[i] > rating[j]
                bigger_r[i] += rating[i] < rating[j]
        ans = 0
        for i in range(n):
            ans += less_l[i] * bigger_r[i] + less_r[i] * bigger_l[i]
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res=0
        for i in range(0,len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if ((rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k])):
                        res+=1
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        stack, ans = [], 0
        for r in rating:
            new = [[r]]
            for team in stack:
                if len(team) == 1:
                    new.append(team + [r])
                elif len(team) == 2:
                    if team[0] < team[1] < r or team[0] > team[1] > r:
                        ans += 1
            stack.extend(new)
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res= 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if rating[j] > rating[i] and rating[k] > rating[j]:
                        res+=1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        res+=1
        return res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        size = len(rating)
        count = 0
        for i in range(size):
            for j in range(i+1,size):
                for k in range(j+1,size):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        count += 1
        return count

import itertools

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        mycom = [c for c in itertools.combinations(rating, 3)]
        ans = 0
        for item in mycom:
            if item[0] < item[1] and item[1] < item[2]:
                ans += 1
            if item[0] > item[1] and item[1] > item[2]:
                ans += 1
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1, len(rating)):
                    if (rating[k]<rating[j])&(rating[j]<rating[i]):
                        count+=1
                    elif (rating[k]>rating[j])&(rating[j]>rating[i]):
                        count+=1
        return count

from itertools import combinations
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c=0
        k=list(combinations(rating,3))
        for i in k:
            if( i[0]<i[1] and i[1]<i[2]) or (i[0]>i[1] and i[1]>i[2]):
                c+=1
        return c

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        size = len(rating)
        count = 0
        for i in range(size):
            for j in range(i + 1, size):
                for k in range(j + 1, size):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        count += 1
                    elif rating[i] > rating[j] and rating[j] > rating[k]:
                        count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        n=len(rating)
        
        if n<3:
            return 0
        
        teams=0
        for x in range(n):
            for y in range(x+1,n):
                for z in range(y+1,n):
                    a,b,c=rating[x],rating[y],rating[z]
                    if (a>b>c) or (a<b<c):
                        teams+=1
        
        return teams


class Solution:
    
    def checkList(self, head: List[List[int]], tail: List[int], init: int) -> int:
        result = init
        head_copy = list(head)
        for i in head_copy:
            num = tail[0]
            ilen = len(i)
            if ilen == 2:
                if (i[0] < i[1] and i[1] < num) or (i[0] > i[1] and i[1] > num):
                    result+=1   
            else:
                head.append(i + [num])    

        if len(tail) == 1: 
            return result
        else:
            return self.checkList(head, tail[1:], result)
        
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3: 
           return 0 
        return self.checkList([[],[rating[0]]], rating[1:], 0)   

class Solution:
    
    def createAscGraph(self, ratings):
        graph = {}
        for index, rating in enumerate(ratings):
            graph[rating] = []
            for rate in ratings[index + 1:]:
                if rate > rating:
                    graph[rating] += [rate]
        return graph
        
    def createDescGraph(self, ratings):
        graph = {}
        for index, rating in enumerate(ratings):
            graph[rating] = []
            for rate in ratings[index + 1:]:
                if rate < rating:
                    graph[rating] += [rate]
        return graph
    
    def count_sequences(self, graph):
        counter = 0
        for key in graph.keys():
            for item in graph[key]:
                for item in graph[item]:
                    counter += 1
                    
        return counter
    
    def numTeams(self, rating: List[int]) -> int:
        asc_graph = self.createAscGraph(rating)
        desc_graph = self.createDescGraph(rating)
        
        return self.count_sequences(asc_graph) + self.count_sequences(desc_graph)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return self.dfs1(rating, []) + self.dfs2(rating, [])

    def dfs1(self, array, path):
        #print(array, path)
        if len(path) == 3:
            return 1
        val = 0
        for i in range(len(array)):
            if not path or path[-1] > array[i]:
                val += self.dfs1(array[i + 1:], path + [array[i]])
        return val

    def dfs2(self, array, path):
        #print(array, path)
        if len(path) == 3:
            return 1
        val = 0
        for i in range(len(array)):
            if not path or path[-1] < array[i]:
                val += self.dfs2(array[i + 1:], path + [array[i]])
        return val

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(0, len(rating)):
            for j in range(i + 1, len(rating)):
                for k in range(j + 1, len(rating)):
                    curr = (rating[i], rating[j], rating[k])
                    if (rating[i] < rating[j] and rating[j] < rating[k]) or (rating[i] > rating[j] and rating[j] > rating[k]): cnt += 1                
        return cnt
                        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        length = len(rating); numberOfTeams = 0
        for i in range(0, length):
            for j in range(0, length):
                if i < j:
                    for k in range(0, length):
                        if j < k:
                            if rating[i] < rating[j] and rating[j] < rating[k]:
                                numberOfTeams = numberOfTeams + 1
                            elif rating[i] > rating[j] and rating[j] > rating[k]:
                                numberOfTeams = numberOfTeams + 1
        return numberOfTeams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(len(rating) - 2):
            for j in range(i, len(rating) - 1):
                for k in range(j, len(rating)):
                    if (rating[i] > rating[j]) & (rating[j] > rating[k]):
                        cnt += 1
                    elif (rating[i] < rating[j]) & (rating[j] < rating[k]):
                        cnt += 1
                    # print([i, j, k], [rating[i], rating[j], rating[k]], cnt)
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        count = 0
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                        count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        length = len(rating)
        for i in range(length - 2):
            for j in range(i, length - 1):
                for k in range(j, length):
                    if rating[i] > rating[j] > rating[k]:
                        cnt += 1
                    if rating[i] < rating[j] < rating[k]:
                        cnt += 1
        return cnt


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        self.ans = 0
        def traverse(idx, arr, direction):
            if len(arr) == 3:
                self.ans +=1
                return
            for j in range(idx, len(rating) - (2-len(arr))):
                
                if direction == 'up' and rating[j] > arr[-1]:
                    traverse(j+1, arr.copy() + [rating[j]], direction)
                if direction == 'down' and rating[j] < arr[-1]:
                    traverse(j+1, arr.copy() + [rating[j]], direction)

        
        for i in range(0, len(rating) -2):
            traverse(i+1, [rating[i]], 'up')
            traverse(i+1, [rating[i]], 'down')
            
        return self.ans
            
        


from itertools import combinations
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for c in combinations([i for i in range(len(rating))],3):
            i,j,k = c[0],c[1],c[2]
            if rating[i] < rating[j] and rating[j] < rating[k]:
                cnt +=1
            if rating[i] > rating[j] and rating[j] > rating[k]:
                cnt +=1
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        team_cand_a = [[] for _ in range(n)]
        a_count = 0
        team_cand_d = [[] for _ in range(n)]
        d_count = 0
        for i in range(n-1):
            for j in range(i+1, n):
                if rating[j] > rating[i]:
                    team_cand_a[i].append([i,j])
                elif rating[j] < rating[i]:
                    team_cand_d[i].append([i,j])
        print(team_cand_a)
        print(team_cand_d)
        for ca in team_cand_a:
            for ij in ca:
                a_count += len(team_cand_a[ij[-1]])
        for cd in team_cand_d:
            for ij in cd:
                d_count += len(team_cand_d[ij[-1]])
        
        return a_count + d_count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        pairs = []
        if len(rating) == 1 or len(rating) == 2:
            return 0
        else:
            for i in range(len(rating)):
                for j in range(i+1,len(rating)):
                    for k in range(j+1,len(rating)):
                        if rating[i] > rating[j] > rating[k]:
                            pairs.append([rating[i],rating[j],rating[k]])
                        elif rating[i] < rating[j] < rating[k]:
                            pairs.append([rating[i],rating[j],rating[k]])
            
            return len(pairs)


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        output = 0
        for item in itertools.combinations([x for x in range(len(rating))],3):
            if rating[item[0]] < rating[item[1]] < rating[item[2]] or rating[item[0]] > rating[item[1]] > rating[item[2]]:
                output += 1
        return output

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        teams = set()
        for i in range(0, len(rating) - 2):
            for j in range(i + 1, len(rating) -1):
                for k in range(j + 1, len(rating)):
                    if (rating[i] < rating[j] < rating[k]):
                        teams.add((i, j, k))
                    if (rating[i] > rating[j] > rating[k]):
                        teams.add((i, j, k))
                        
        return len(teams)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        output = 0
        for item in itertools.combinations([x for x in range(len(rating))],3):
            #print(item)
            if rating[item[0]] < rating[item[1]] < rating[item[2]] or rating[item[0]] > rating[item[1]] > rating[item[2]]:
                output += 1
        return output        

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = []
        n = len(rating)
        for i in range(n):
            for j in range(i,n):
                for k in range(j,n):
                    if rating[i] < rating[j]:
                        if rating[j] < rating[k]:
                            ans.append([rating[i], rating[j], rating[k]])
                    if rating[i] > rating[j]:
                        if rating[j] > rating[k]:
                            ans.append([rating[i], rating[j], rating[k]])

        return len(ans)

from itertools import combinations
class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        ### Store the index in dictionary 
        from itertools import combinations
        output = 0
        for item in combinations([x for x in range(len(rating))],3):
            if rating[item[0]] < rating[item[1]] < rating[item[2]] or rating[item[0]] > rating[item[1]] > rating[item[2]]:
                output += 1
        return output
#         dic = {}
#         for i, x in enumerate(rating):
#             dic[x] = i
#         rating.sort()
#         cnt = 0
#         combinations = list(combinations(rating,3))

#         for comb in combinations:
#             if (dic[comb[0]] < dic[comb[1]] and dic[comb[1]] < dic[comb[2]]) or (dic[comb[0]] > dic[comb[1]] and dic[comb[1]] > dic[comb[2]]):
                
#                 cnt += 1
#         return cnt
    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        count = [0]
        def generate(team,pos,method):
            if len(team)==3:
                count[0]+=1
                return
            else:
                for i in range(pos,n):
                    if team!=[]:
                        if method=='i':
                            if rating[i]>team[-1]:
                                generate(team+[rating[i]],i+1,method)
                            else:
                                continue
                        elif method=='d':
                            if rating[i]<team[-1]:
                                generate(team+[rating[i]],i+1,method)
                            else:
                                continue
                    if team==[]:
                        generate(team+[rating[i]],i+1,method)
        generate([],0,'i')
        generate([],0,'d')
        return count[0]

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        ans+=1
        return ans
            


import itertools
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        candidates = list(combinations(rating, 3))
        return sum([candidate[0] <= candidate[1] <= candidate[2] or candidate[0] >= candidate[1] >= candidate[2] for candidate in candidates])

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            l = [0,0]
            g = [0,0]
            for j in range(len(rating)):
                if i!=j:
                    if rating[j] < rating[i]:
                        l[i<j]+=1
                    if rating[j] > rating[i]:
                        g[i<j]+=1
            count+= l[0]*g[1] + l[1]*g[0]
        return count


def findmyTeams(myrating: List[int], member_list: List[int], current_member: int) -> int:
  my_new_member_list = member_list.copy()
  if(len(member_list) == 3):
    #print(member_list)
    return 1
  elif(len(myrating) == 0):
    return 0
  
  score = 0
  for a in range(len(myrating)):
    if(myrating[a] > current_member):
      #print(myrating[a], current_member)
      my_new_member_list.append(myrating[a])
      score += findmyTeams(myrating[a:], my_new_member_list, myrating[a])
      my_new_member_list.pop()
  
  return score


class Solution:
  def numTeams(self, rating: List[int]) -> int:
    #We will iterate through the list from left to right first.
    #So that means we will have two for loops
    answer = 0
    for i in range(len(rating)):
      answer += findmyTeams(rating[i:], [rating[i]], rating[i])
    
    #print(\"Normal:\", answer)
    
    rating.reverse()
    for i in range(len(rating)):
      answer += findmyTeams(rating[i:], [rating[i]], rating[i])
      
      
    #print(\"Reversed: \", answer)
    
    
    return(answer)


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        output = 0
        for item in itertools.combinations([x for x in range(len(rating))],3):
            if rating[item[0]] < rating[item[1]] < rating[item[2]] or rating[item[0]] > rating[item[1]] > rating[item[2]]:
                output += 1
        return output
            


class Solution:
    
    def checkList(self, head: List[List[int]], tail: List[int], init: int) -> int:
        result = init
        head_copy = head.copy()
        for i in head_copy:
            num = tail[0]
            ilen = len(i)
            if ilen == 2:
                if (i[0] < i[1] and i[1] < num) or (i[0] > i[1] and i[1] > num):
                    result+=1   
            elif ilen < 2:
                head.append(i + [num])    

        if len(tail) == 1: 
            return result
        else:
            return self.checkList(head, tail[1:], result)
        
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3: 
           return 0 
        return self.checkList([[]], rating, 0)    

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        num = 0
        for i in range(len(rating)):
            for j in range(i + 1, len(rating)):
                for k in range(j + 1, len(rating)):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        num += 1
        return num


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        self.res = 0
        for i in range(len(rating)):
            self.dfs_increase([rating[i]], rating[i+1:], 1)
            self.dfs_decrease([rating[i]], rating[i+1:], 1)
        return self.res
    
    def dfs_increase(self, stack, rating, count):
        if len(stack) == 3:
            self.res += 1
            return
        for i in range(len(rating)):
            if rating[i] > stack[-1]:
                self.dfs_increase(stack + [rating[i]], rating[i+1:], count + 1)
    
    def dfs_decrease(self, stack, rating, count):
        if len(stack) == 3:
            self.res += 1
            return
        for i in range(len(rating)):
            if rating[i] < stack[-1]:
                self.dfs_decrease(stack + [rating[i]], rating[i+1:], count + 1)


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        
        ratingCount = 0
        for i in range (0, len(rating) - 2):
            for j in range (i+1, len(rating) - 1):
                for k in range (j+1, len(rating)):
                    if rating[i] > rating[j] > rating[k] or rating[i] < rating[j] < rating[k]:
                        ratingCount += 1
        
        return ratingCount

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        teams = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                for k in range(j+1,n):
                    if(rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]):
                        teams += 1
        
        return teams



class Solution:
    def numTeams(self, rating):
        length = len(rating)
        num_combinations = 0
        for i in range(length - 2):
            for j in range(i + 1, length - 1):
                for k in range(j + 1, length):
                    if rating[i] < rating[j]:
                        if rating[j] < rating[k]:
                            num_combinations = num_combinations + 1
                    elif rating[i] > rating[j]:
                        if rating[j] > rating[k]:
                            num_combinations = num_combinations + 1
        return num_combinations





class Solution:
    def _is_valid_team(self, rating: List[int], i: int, j: int, k: int) -> bool:
        if rating[i] < rating[j] and rating[j] < rating[k]:
            return True
        
        if rating[i] > rating[j] and rating[j] > rating[k]:
            return True
        
        return False

    def numTeams(self, rating: List[int]) -> int:
        num_teams = 0
        
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if self._is_valid_team(rating, i, j, k):
                        num_teams += 1
                        
        return num_teams

class Solution:
    def numTeams(self, arr: List[int]) -> int:
        k = 3
        self.memo = {}; ans = 0
        
        for i in range(len(arr)):
            ans += self.helper(i, arr, k-1, True)
        
        self.memo = {}
        for i in range(len(arr)):
            ans += self.helper(i, arr, k-1, False)
        
        return ans
    
    def helper(self, i, arr, k, lookForIncreasing):
        if k == 0:
            return 1
        
        if i == len(arr):
            return 0
        
        if (i, k) in self.memo:
            return self.memo[(i, k)]
        
        res = 0
        for j in range(i+1, len(arr)):
            if arr[j] > arr[i] and lookForIncreasing:
                res += self.helper(j, arr, k-1, lookForIncreasing)
            
            elif arr[j] < arr[i] and not lookForIncreasing:
                res += self.helper(j, arr, k-1, lookForIncreasing)
        
        self.memo[(i, k)] = res
        return res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(0, len(rating)-2):
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        count += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        count +=1
                    
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        # rating.sort()
        def ascend(nums, curLargest, count):
            if count == 3:
                return 1
            if not nums:
                return 0
            total = 0
            for i in range(len(nums)):
                if nums[i] > curLargest:
                    total += ascend(nums[i+1:], nums[i], count+1)
            return total
        
        def descend(nums, curSmallest, count):
            if count == 3:
                return 1
            if not nums:
                return 0
            total = 0
            for i in range(len(nums)):
                if nums[i] < curSmallest:
                    total += descend(nums[i+1:], nums[i], count+1)
            return total
        
        return ascend(rating, 0, 0) + descend(rating, float('inf'), 0)
                
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)-1):
                for k in range(j+1,len(rating)):
                    if rating[i]<rating[j] or rating[i] > rating[j]:
                        if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                            if rating[j] < rating[k] or rating[j] > rating[k]:
                                count=count+1
        return count



class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(len(rating)):
            for j in range(i,len(rating)):
                for k in range(j,len(rating)):
                    if rating[i] > rating[j] > rating[k] or rating[i] < rating[j] < rating[k]:
                        cnt += 1
        return cnt
                        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        total = 0
        n = len(rating)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        total = total + 1
        return total

from itertools import combinations
import numpy as np
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        rating=np.array(rating)
        for i in range(len(rating)):
            if (sum(rating[i]<rating[i+1:])>=2):
                soldiers=[x for x in rating[i+1:] if x>rating[i]]
                comb_soldiers=combinations(soldiers,2)
                count=count+len([comb for comb in comb_soldiers if list(comb)==sorted(comb)])

            
            if (sum(rating[i]>rating[i+1:])>=2):
                soldiers=[x for x in rating[i+1:] if x<rating[i]]
                comb_soldiers=combinations(soldiers,2)
                count=count+len([comb for comb in comb_soldiers if list(comb)==sorted(comb, reverse=True)])
        return count
            
            


class Solution:
    res = 0
    def numTeams(self, rating: List[int]) -> int:
        
        def dfs(rating, start, prev):
            if len(prev) == 3:
                self.res += 1
                return
            for i in range(start, len(rating)):
                if not prev or prev[-1] < rating[i]:
                    dfs(rating, i+1, prev + [rating[i]])
        
        dfs(rating, 0, [])
        dfs(rating[::-1], 0, [])
        return self.res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        res += self.increse_dfs(rating, [], 0)
        res += self.decrese_dfs(rating, [], 0)
        
        return res
        
        
    def increse_dfs(self, rating: List[int], tmp: List[int], res: int) -> int:
        if len(tmp) == 3:
            res += 1 
            return res
        if len(rating) == 0:
            return res
        
        for idx, n in enumerate(rating):
            if len(tmp) == 0:
                tmp.append(n)
                res = self.increse_dfs(rating[idx+1:], tmp, res)
                tmp.pop()
            else:
                if n > tmp[-1]:
                    tmp.append(n)
                    res = self.increse_dfs(rating[idx+1:], tmp, res)
                    tmp.pop()
        return res
    
    def decrese_dfs(self, rating: List[int], tmp: List[int], res: int) -> int:
        if len(tmp) == 3:
            res += 1 
            return res
        if len(rating) == 0:
            return res
        
        for idx, n in enumerate(rating):
            if len(tmp) == 0:
                tmp.append(n)
                res = self.decrese_dfs(rating[idx+1:], tmp, res)
                tmp.pop()
            else:
                if n < tmp[-1]:
                    tmp.append(n)
                    res = self.decrese_dfs(rating[idx+1:], tmp, res)
                    tmp.pop()

        return res
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        teams = []
        
        for i in range(0, len(rating)):
            for j in range(i + 1, len(rating)):
                for k in range(j + 1, len(rating)):
                    curr = (rating[i], rating[j], rating[k])
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        teams.append(curr)
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        teams.append(curr)
                        
        # print(teams)
        return len(teams)
                        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        n = len(rating)
        for i in range(n-2):
            for j in range(i,n-1):
                if rating [i] < rating[j] or rating[i] > rating[j]:
                    for k in range(j, n):
                        if rating[i] < rating[j] < rating[k]: teams += 1
                        if rating[i] > rating[j] > rating[k]: teams += 1
                            
        return teams

class node:
    
    def __init__(self,val):
        
        self.val = val
        
        self.right = None
        
        self.left = None

class Solution:
    
    def update(self,i,j,ind,root):
    
        if i == j:
            root.val += 1
        else:
            
            mid = (i+j) // 2
            
            if ind <=mid:
                self.update(i,mid,ind,root.left)
            elif ind > mid:
                self.update(mid+1,j,ind,root.right)
                
            root.val = 0
            
            if root.left:
                root.val +=root.left.val
            if root.right:
                root.val += root.right.val
                
                
      
    def findSum(self,i,j,left,right,root):
        
        if left<=i and right>=j:
            return root.val
        
        elif right<i or left > j:
            return 0
        
        mid = (i+j) // 2
        
        if right<=mid:
            return self.findSum(i,mid,left,right,root.left)
        elif left>mid:
            return self.findSum(mid+1,j,left,right,root.right)
        
        else:
            
            x = self.findSum(i,mid,left,mid,root.left)
            
            y = self.findSum(mid+1,j,mid+1,right,root.right)
            
            return x+y
        
    
    def build(self,i,j):
        
        if i == j:
            root = node(0)
            
        else:
            
            mid = (i+j) // 2
            root = node(0)
            root.left = self.build(i,mid)
            root.right = self.build(mid+1,j)
            
            
            
            if root.left:
                root.val+=root.left.val
                
            if root.right:
                root.val+=root.right.val
                
                
        return root
            
   
    def solve(self,rating):
        n = max(rating) + 1
        
        self.arr = [0]*n
        
        length = len(rating)
        
        left = [0]*length
        right = [0]*length
        rootLeft = self.build(0,n)
        rootRight = self.build(0,n)
        
        
        for i in range(length):
            
            left[i] = self.findSum(0,n,0,rating[i]-1,rootLeft)
            self.update(0,n,rating[i],rootLeft)
                
        for i in range(length-1,-1,-1):
            
            right[i] = self.findSum(0,n,rating[i]+1,n,rootRight)
            self.update(0,n,rating[i],rootRight)
            
        
        ans = 0
        for i in range(1,length-1):
            
            ans = ans + left[i]*right[i]
        
        # print(left)
        # print(right)
        # print(\"************\")
        return ans
        
    def numTeams(self, rating: List[int]) -> int:
        
        if len(rating)<3:
            return 0
        
        temp = rating[:]
        temp.sort()
        
        value = 1
        
        self.mp = {}
        
        for x in temp:
            
            if x not in self.mp:
                
                self.mp[x] = value
                
                value +=1
                
            
        for i in range(len(rating)):
            
            rating[i] = self.mp[rating[i]]
            
            
        
        ans = self.solve(rating)+self.solve(rating[::-1])
        
        return ans
        
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        team = 0
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)-1):
                for k in range(j+1, len(rating)):
                    if (rating[i]>rating[j]) and (rating[j]>rating[k]):
                        team = team + 1
                    elif (rating[i]<rating[j]) and (rating[j]<rating[k]):
                        team = team + 1
        return team

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)-2):
            for j in range(i, len(rating)-1):
                for k in range(j, len(rating)):
                    if ((rating[i] < rating[j] and rating[j] < rating[k]) or
                        (rating[i] > rating[j] and rating[j] > rating[k])):
                        count+=1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                        if((rating[i]>rating[j] and rating[j]>rating[k]) or (rating[i]<rating[j] and rating[j]<rating[k])):
                            count += 1
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        dobar = 0
        for i in range(n-2):
            for j in range(i+1,n-1):
                for k in range(j+1,n):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        dobar += 1
        return dobar

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(0,len(rating)-2):
            for j in range(i,len(rating)-1):
                for k in range(j,len(rating)):
                    if rating[i]<rating[j]<rating[k]:
                        count+=1
                    elif rating[i]>rating[j]>rating[k]:
                        count+=1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        
        ratings = [[]]
        
#         for items in rating:            
#             ratings += [item + [items] for item in ratings if len(item) < 3]
          
#         count = 0
#         for item in ratings:
#             if len(item) == 3:
#                 if item[0] > item[1] and item[1] > item[2]:
#                     count += 1
#                 elif item[0] < item[1] and item[1] < item[2]:
#                     count += 1

        n = len(rating)

        count = 0
        for index_1 in range(0, n):            
            for index_2 in range(index_1+1, n):                
                for index_3 in range(index_2+1, n):
                    if rating[index_1] < rating[index_2] and rating[index_2] < rating[index_3]:
                        count += 1
                        
        for index_1 in range(n-1, -1, -1):  
            for index_2 in range(index_1-1, -1, -1):  
                for index_3 in range(index_2 -1, -1, -1):
                    if rating[index_1] < rating[index_2] and rating[index_2] < rating[index_3]:
                        count += 1
                
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        l = len(rating)
        for i in range(0, l - 2):
            for j in range(i + 1, l - 1):
                for k in range(j + 1, l):
                    if (rating[i] < rating[j] and rating[j] < rating[k]) or (rating[i] > rating[j] and rating[j] > rating[k]):
                        res += 1

        return res

class Solution:
    def solve_inc(self, rating, count, idx, last):
        if(count == 3):
            return 1
        if(idx >= len(rating)):
            return 0
        if(rating[idx] > last):
            return self.solve_inc(rating, count+1, idx+1, rating[idx]) + self.solve_inc(rating, count, idx+1, last)
        else:
            return self.solve_inc(rating, count, idx+1, last)
    def solve_dec(self, rating, count, idx, last):
        if(count == 3):
            return 1
        if(idx >= len(rating)):
            return 0
        if(rating[idx] < last):
            return self.solve_dec(rating, count+1, idx+1, rating[idx]) + self.solve_dec(rating, count, idx+1, last)
        else:
            return self.solve_dec(rating, count, idx+1, last)
    def numTeams(self, rating: List[int]) -> int:
        idx = 0
        res = 0
        # print(self.solve_inc(rating, 1, 1, rating[0]))
        for i in range(len(rating)):
            res += self.solve_inc(rating, 1, i+1, rating[i])
            res += self.solve_dec(rating, 1, i+1, rating[i])
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # brute force
        n = len(rating)
        total = 0
        for i in range(n):
            for j in range(i,n):
                for k in range(j,n):
                    total += any([
                        rating[i] < rating[j] < rating[k],
                        rating[i] > rating[j] > rating[k]
                    ])   
        return total

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        count = 0
        
        for i in range(n):
            for j in range(i+1,n-1):
                for k in range(j+1,n):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        count +=1
        return count                

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        
        for i in range(len(rating)):
            for j in range(len(rating)):
                if 0 <= i < j:
                    for k in range(len(rating)):
                        if j < k < len(rating):
                            if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                                result += 1
        
        return result


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        from itertools import combinations
        
        def satisfies_condition(inp):
            if inp[0] < inp[1] < inp[2] or inp[0] > inp[1] > inp[2]:
                return True
        
        team_count = 0
        for x in list(combinations(rating, 3)):
            team_count += 1 if satisfies_condition(x) else 0
        
        return team_count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        possible_list = []
        count = 0
        for i, first_num in enumerate(rating[:-2]):
            for j, sec_num in enumerate(rating[i+1:-1]):
                for k, third_num in enumerate(rating[j+i+2:]):
                    possible_list.append((first_num, sec_num, third_num))
        for pair in possible_list:
            if pair[0] > pair[1] > pair[2] or pair[2] > pair[1] > pair[0]:
                count += 1
        return count



class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        #s1: recursive approach, needs to be made into dp
        
        def solve(arr,n,k,arr_max):

            #base condition
            if k==0:
                return 1

            if n==len(arr):
                return 0

            #recursive logic
            if arr[n] > arr_max:
                return solve(arr,n+1,k-1,arr[n]) + solve(arr,n+1,k,arr_max)
            else:
                return solve(arr,n+1,k,arr_max)
        
        return solve(rating,0,3,0)+solve(rating[::-1],0,3,0)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        total = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        total += 1
                    elif rating[i] < rating[j] and rating[j] < rating[k]:
                        total += 1
        return total

class Solution:
    def solve_inc(self, rating, count, idx, last):
        if(count == 3):
            return 1
        if(idx >= len(rating)):
            return 0
        if(rating[idx] > last):
            return self.solve_inc(rating, count+1, idx+1, rating[idx]) + self.solve_inc(rating, count, idx+1, last)
        else:
            return self.solve_inc(rating, count, idx+1, last)
    def solve_dec(self, rating, count, idx, last):
        if(count == 3):
            return 1
        if(idx >= len(rating)):
            return 0
        if(rating[idx] < last):
            return self.solve_dec(rating, count+1, idx+1, rating[idx]) + self.solve_dec(rating, count, idx+1, last)
        else:
            return self.solve_dec(rating, count, idx+1, last)
    def numTeams(self, rating: List[int]) -> int:
        idx = 0
        res = 0
        for i in range(len(rating)):
            res += self.solve_inc(rating, 1, i+1, rating[i])
            res += self.solve_dec(rating, 1, i+1, rating[i])
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        stack=[]
        list1=[]
        n=len(rating)
        for i in range(0,n-2):
            # check 3 items from in the list iterating using i,j,k.i until n-2,j until n-1 and k untill n
            for j in range(i+1,n-1):
                for k in range(j+1,n):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        stack.append(rating[i])
                        stack.append(rating[j])
                        stack.append(rating[k])
                        #print(\"stack\",stack)
                        list1.append(stack)
                    stack=[]
        #print(list1)
        return len(list1)
                
                        


class Solution:
    def numTeams(self, a: List[int]) -> int:
        list1=[]
        for i in range(len(a)-2):
            for j in range(i+1,len(a)-1):
                for k in range(j+1,len(a)):
                    if a[i]<a[j]<a[k]:
                        list1.append((a[i],a[j],a[k]))
                    if a[i]>a[j]>a[k]:
                        list1.append((a[i],a[j],a[k]))
        return len(list1)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ratingLen = len(rating)
        result = 0
        for i in range(ratingLen-2):
            for j in range(i+1, ratingLen-1):
                for k in range(j+1, ratingLen):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        result += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        result += 1
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                for k in range(j+1,len(rating)):
                    if self.check(rating[i],rating[j],rating[k]):
                        # print(rating[i],rating[j],rating[k])
                        count+=1
        return count
    
    def check(self,i,j,k):
        if i<j and j<k:
            return True
        elif i>j and j>k:
            return True
        else:
            return False

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        nTeams = 0
        for i in range(len(rating)):
            for j in range(i, len(rating)):
                for k in range(j, len(rating)):
                    if rating[j] > rating[i]:
                        if rating[k] > rating[j]:
                            nTeams += 1
                    elif rating[j] < rating[i]:
                        if rating[k] < rating[j]:
                            nTeams += 1
        return nTeams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        
        if n < 3:
            return 0
        
        results = 0
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range (j + 1, n):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        results += 1
                    elif rating[i] > rating[j] and rating[j] > rating[k]:
                        results +=1
        return results

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        l = []
        x = 0

        while x <= len(rating)-2:
            y = x + 1
            while y <= len(rating)-1:
                z = y + 1
                while z < len(rating):
                    if rating[x] < rating[y] and rating[y] < rating[z]:
                        teams += 1
                        l.append([rating[x], rating[y], rating[z]])
                    elif rating[x] > rating[y] and rating[y] > rating[z]:
                        teams += 1
                        l.append([rating[x], rating[y], rating[z]])

                    z += 1
                y += 1
            x += 1

    
        return teams
    


class Solution:    
    def numTeams(self, ratings: List[int]) -> int:
        #maintain a data structure where dict[index] stores another dict keyed by ranking (r) \\
        #and stores number of rankings greater than that ranking in the rating list
        res = 0
        
        numRatings = len(ratings)
        sortedRatings = sorted(ratings)
        
        mapping = dict()
        mapping_rev = dict()
        mapping[len(ratings)] = dict(list(zip(ratings,[0]*numRatings)))
        mapping_rev[len(ratings)] = dict(list(zip(ratings,[0]*numRatings)))
        for index, rating in list(enumerate(ratings))[::-1]:
            mapping[index] = dict()
            mapping_rev[index] = dict()
            for tmpRating in ratings:
                if tmpRating < rating:
                    mapping[index][tmpRating] = mapping[index+1][tmpRating] + 1
                    mapping_rev[index][tmpRating] = mapping_rev[index+1][tmpRating]
                else:
                    mapping[index][tmpRating] = mapping[index+1][tmpRating]
                    mapping_rev[index][tmpRating] = mapping_rev[index+1][tmpRating] + 1
        
        for i, rating_i in list(enumerate(ratings)):
            #check triplets starting with rating[i]
            for j, rating_j in list(dict(list(zip(list(range(i+1,numRatings+1)), ratings[i+1:]))).items()):
                if rating_j > rating_i:
                    res += mapping[j+1][rating_j]
                else:
                    res += mapping_rev[j+1][rating_j]
        
        return res
            
                
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        def loop(prev, remains, i):
            res = 0
            if i >= len(rating):
                return res
            if rating[i] > prev:
                if remains == 1:
                    res += 1
                else:
                    res += loop(rating[i], remains-1, i+1)
            res += loop(prev, remains, i+1)
            return res
        res = 0
        res += loop(-1, 3, 0)
        rating.reverse()
        res += loop(-1, 3, 0)
        return res

class Solution:
    def validTriple(self, a,b,c):
        if (a < b and b < c) or (c < b and b < a):
            return True
        return False
        
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                for k in range(j+1, len(rating)):
                    if self.validTriple(rating[i], rating[j], rating[k]):
                        ans += 1
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        i = 0
        j = i + 1
        k = j+1
        result = 0
        while (i < len(rating)- 2):
            if k == len(rating):
                j += 1
                k = j

            if (j == len(rating)):
                i += 1
                j = i + 1
                k = j

            if rating[i] < rating[j] and rating[j] < rating[k]:
                result += 1
            elif rating[i] > rating[j] and rating[j] > rating[k]:
                result += 1



            k+= 1
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        sum = 0
        for i in range(len(rating)):
            for j in range(i,len(rating)):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] < rating[k]:
                        sum += 1
                    if rating[len(rating)-1-i] < rating[len(rating)-1-j] < rating[len(rating)-1-k]:
                        sum+=1
        return sum


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        n = len(rating)
        for i in range(n-2):
            for j in range(i,n-1):
                for k in range(j, n):
                    if i < j < k:
                        if rating[i] < rating[j] < rating[k]: teams += 1
                        if rating[i] > rating[j] > rating[k]: teams += 1
                            
        return teams

class Solution:
    
    def checkList(self, head, tail, init: int) -> int:
        result = init
        head_copy = head.copy()
        for i in head_copy:
            num = tail[0]
            ilen = len(i)
            if ilen > 0:
                if ilen == 2:
                    if i[0] < i[1] and i[1] < num:
                        result+=1   
                    if i[0] > i[1] and i[1] > num:
                        result+=1
                elif ilen == 1:
                    head.append(i + [num])   
            else:
                head.append([num])       

        if len(tail) == 1: 
            return result
        else:
            del tail[0]
            return self.checkList(head, tail, result)
        
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3: 
           return 0 
        list = [[]]
        return self.checkList(list, rating, 0)    

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # Backtrack for positive and backtrack for negative
        res  = []
        n = len(rating)
        
        def btInc(index: int, curr: List[int]):
            if len(curr) == 3:
                res.append(curr)
                return
            
            for i in range(index+1, n):
                if curr==[] or rating[i]> curr[-1]:
                    btInc(i, curr+[rating[i]])
        
        def btDec(index: int, curr: List[int]):
            if len(curr) == 3:
                res.append(curr)
                return
            
            for i in range(index+1, n):
                if curr==[] or rating[i] < curr[-1]:
                    btDec(i, curr+[rating[i]])
                    
        btInc(-1,[])
        btDec(-1,[])
        
        return len(res)
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        for i in range(len(rating) - 2):
            for j in range(i, len(rating) - 1):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] and rating[j] < rating[k]:
                        res += 1
                    if rating[i] > rating[j] and rating[j] > rating[k]:
                        res += 1
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c = 0
        for i,v in enumerate(rating[1:-1]):
            llc = rgc = lgc = rlc = 0
            for l in rating[:i+1]:
                if l < v:
                    llc += 1
                elif l > v:
                    lgc += 1
            for r in rating[i+2:]:
                if r > v:
                    rgc += 1
                elif r < v:
                    rlc += 1
            c += llc * rgc + lgc * rlc           
        return c


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i, r in enumerate(rating):
            if i >= len(rating) - 2:
                break
            
            # check asc
            li = [val for val in rating[i + 1:] if val > r]
            for j, r2 in enumerate(li):
                li2 = [val for val in li[j + 1:] if val > r2]
                cnt += len(li2)

            # check desc
            li = [val for val in rating[i + 1:] if val < r]
            for j, r2 in enumerate(li):
                li2 = [val for val in li[j + 1:] if val < r2]
                cnt += len(li2)
            
        return cnt
    
        
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            l = [rating[i]]
            for j in range(i+1,len(rating)):
                l.append(rating[j])
                for k in range(j+1,len(rating)):
                    l.append(rating[k])
                    if (l[0] > l[1] and l[1] > l[2]) or (l[0] < l[1] and l[1] < l[2]):
                        count += 1
                    l = l[:2]
                l = l[:1]
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return self.sumHigh(rating)

    def sumHigh(self, rating: List[int]) -> int:
        sum = 0
        for i in range(len(rating)):
            for j in range(i,len(rating)):
                for k in range(j, len(rating)):
                    if rating[i] < rating[j] < rating[k]:
                        sum += 1
                    if rating[len(rating)-1-i] < rating[len(rating)-1-j] < rating[len(rating)-1-k]:
                        sum+=1
        return sum
    
    def sumLow(self, rating: List[int]) -> int:
        sum = 0
        for i in range(len(rating)-1, -1, -1):
            for j in range(i,-1, -1):
                for k in range(j, -1, -1):
                    if rating[i] < rating[j] < rating[k]:
                        sum += 1   
        return sum

class Solution:
    def numTeams(self, a: List[int]) -> int:
        
        def rec(a, start, path, res):
                        
            for i in range(start, len(a)):
                
                if len(path) == 0:
                    path.append(a[i])
                    rec(a, i + 1, path, res)
                    path.pop()
                    
                elif len(path) == 1:
                    if a[i] != path[-1]:
                        path.append(a[i])
                        rec(a, i + 1, path, res)
                        path.pop()
                                                                                
                elif len(path) == 2:
                    if path[0] < path[1] and path[1] < a[i]:
                        path.append(a[i])
                        res[0] += 1
                        path.pop()
                        
                    elif path[0] > path[1] and path[1] > a[i]:
                        path.append(a[i])
                        res[0] += 1
                        path.pop()
                        
            return
        
        res = [0]
        rec(a, 0, [], res)
        
        return res[0]
                        
                    
                
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        
        def backtrack(rating, cur, index):
            
            if len(cur) == 3:
                self.count += 1
                return
            
            if len(cur) > 3:
                return
            
            for i in range(index, len(rating)):
                if len(cur) == 2 and cur[0] < cur[1] and rating[i] < cur[1]:
                    continue
                if len(cur) == 2 and cur[0] > cur[1] and rating[i] > cur[1]:
                    continue
                    
                backtrack(rating, cur + [rating[i]], i + 1)
        
        
        self.count = 0
        backtrack(rating, [], 0)
        return self.count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        def checkLess(a,b,c):
            return rating[a] < rating[b] < rating[c]
        def checkG(a,b,c):
            return rating[a] > rating[b] > rating[c]
        if len(rating) < 3: return 0
        if len(rating) == 3:
            if checkLess(0,1,2) or checkG(0,1,2):
                return 1
            return 0
        
        result = 0
        n = len(rating)
        for i in range(n):
            for j in range(i,n):
                for k in range(j, n):
                    if checkLess(i,j,k) or checkG(i,j,k):
                        result += 1
                
        return result


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        i = 0
        j = 1 
        k = 2
        while i < len(rating) - 2:
            if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                res += 1
            k += 1
            if k > len(rating) - 1:
                j += 1
                k = j + 1
            if j > len(rating) - 2:
                i += 1
                j = i + 1
                k = i + 2
        return res

from itertools import combinations
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        indices = list(range(0, len(rating)))
        all_combs = combinations(indices,3)
        result = 0
        for comb in all_combs:
            if comb[0] < comb[1] and comb[1] < comb[2]:
                if rating[comb[0]] < rating[comb[1]] and rating[comb[1]] < rating [comb[2]]:
                    result += 1
                elif rating[comb[0]] >rating[comb[1]] and rating[comb[1]] > rating[comb[2]]:
                    result += 1
        return result
            
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        counter = 0
        for i in range(len(rating)):
            for j in range(len(rating)):
                for k in range(len(rating)):
                    #print(f\"Testing: {rating[i]} {rating[j]} {rating[k]}\")
                    if(i < j and j < k):
                        if(rating[i] < rating[j] and rating[j] < rating[k]):
                            #print(f\"Counting up1 {counter}\")
                            counter += 1
                        elif(rating[i] > rating[j] and rating[j] > rating[k]):
                            #print(f\"Counting up2 {counter}\")
                            counter += 1
        
        return counter

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        z=len(rating)
        final=[]
        if z<3 :
            return 0
        for i in range (0,z):
            for j in range (i+1,z):
                for k in range (j+1,z):
                    if  (rating[i]<rating[j] and rating[j]<rating[k]) or (rating[i]>rating[j] and rating[j]>rating[k]) :
                        final.append((i,j,k))
                        
        final=set(final)
        return len(final)
                        
            
                        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        teams = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                if(rating[i] == rating[j]):
                    continue
                for k in range(j+1,n):
                    if(rating[i] == rating[k] or rating[j] == rating[k]):
                        continue
                    if(rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]):
                        teams += 1
        
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i, r in enumerate(rating):
            if i >= len(rating) - 2:
                break
            
            # check asc
            li = [val for val in rating[i + 1:] if val > r]
            for j, r2 in enumerate(li):
                li2 = [val for val in li[j + 1:] if val > r2]
                cnt += len(li2)
                
#                 if li2:
#                     print(r, r2, li2)
            
            # if li:
            #     cnt += self.count_comb(li, r, True)
            
            # check desc
            li = [val for val in rating[i + 1:] if val < r]
            for j, r2 in enumerate(li):
                li2 = [val for val in li[j + 1:] if val < r2]
                cnt += len(li2)
            
#                 if li2:
#                     print(r, r2, li2)
            
            # if li:
            #     cnt += self.count_comb(li, r, False)
            
        return cnt
    
    
    def count_comb(self, li, num, asc):
        cnt = 0
        
        for i, r in enumerate(li):
            if i >= len(li) - 1:
                break
            
            if asc:
                for j in range(i + 1, len(li)):
                    if num < li[j]:
                        cnt += 1
            else:
                for j in range(i + 1, len(li)):
                    if num > li[j]:
                        cnt += 1

        return cnt
        
            


class Solution:
    def numTeams(self, ratings: List[int]) -> int:
        teams = []
        for i1, r1 in enumerate(ratings):
            for si2, r2 in enumerate(ratings[i1+1:]):
                i2 = i1+1+si2
                for r3 in ratings[i2+1:]:
                    teams.append((r1, r2, r3))
        n = 0
        for i, j, k in teams:
            if i<j<k or i>j>k:
                n +=1
 
        return n

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        teams = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                if(rating[i] == rating[j]):
                    continue
                for k in range(j+1,n):
                    if(rating[i] == rating[k]):
                        continue
                    if(rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]):
                        teams += 1
        
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c = 0
        for i in range(len(rating)):
            j = i + 1
            while(j<len(rating)):
                k= j + 1
                while(k<len(rating)):    
                    if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                        c += 1
                    k += 1
                
                j += 1
        
        return c
                        
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        counter = 0
        
        for i in range(len(rating)):
            for j in range(len(rating)):
                for k in range(len(rating)):
                    if i < j < k:
                        if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
                            counter += 1
        
        return counter


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        c=0
        for i in range(len(rating)):
            for j in range(len(rating)):
                for k in range(len(rating)):
                    if i<j<k:
                        if rating[i]>rating[j]>rating[k] or rating[i]<rating[j]<rating[k]:
                            c+=1
        return c


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        def helper(team, rem):
            if len(team)==3:
                self.count+=1
                return
            
            for i in range(len(rem)):
                if len(team)==1:
                    helper(team+[rem[i]], rem[i:])
                else:
                    if team[-2]<team[-1]:
                        if rem[i]>team[-1]:
                            helper(team+[rem[i]],rem[i:])
                    elif team[-2]>team[-1]:
                        if rem[i]<team[-1]:
                            helper(team+[rem[i]],rem[i:])
            
        self.count=0
        for i in range(len(rating)):
            helper([rating[i]],rating[i:])
        return self.count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)):
            for j in range(len(rating)):
                for k in range(len(rating)):
                    if i<j<k:
                        if rating[i]>rating[j]>rating[k] or rating[i]<rating[j]<rating[k]:
                            count+=1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        def combination(rating, tmp, index, ans, target):
            if len(tmp) == target:
                ans.append(tmp[:])
                return
            for i in range(index, len(rating)):
                if len(tmp) == 2 and not (tmp[0] > tmp[1] > rating[i] or rating[i] > tmp[1] > tmp[0]):
                    continue
                tmp.append(rating[i])
                combination(rating, tmp, i + 1, ans, target)
                tmp.pop()

        possibles = []
        combination(rating, [], 0, possibles, 3)

        count = 0
        for a, b, c in possibles:
            if a < b < c or a > b > c:
                count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams_all = list(itertools.combinations(rating, 3))
        valid_teams = []
        for team in teams_all:
            if team[0] > team[1] > team[2] or team[0] < team[1] < team[2]:
                valid_teams.append(team)
        return len(valid_teams)
                         


from itertools import combinations
class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        ### Store the index in dictionary 
        from itertools import combinations

        dic = {}
        for i, x in enumerate(rating):
            dic[x] = i
        rating.sort()
        cnt = 0
        combinations = list(combinations(rating,3))
        
        
        for comb in combinations:
            if (dic[comb[0]] < dic[comb[1]] and dic[comb[1]] < dic[comb[2]]) or (dic[comb[0]] > dic[comb[1]] and dic[comb[1]] > dic[comb[2]]):
                
                cnt += 1
        return cnt
    
    
    
        # for i in range(len(rating)-2):
        #     print(dic[rating[i]], dic[rating[i + 1]], dic[rating[i + 2]])
        #     if dic[rating[i]] < dic[rating[i + 1]] and dic[rating[i + 1]] < dic[rating[i+ 2]]:
        #         print(dic[rating[i]], dic[rating[i + 1]], dic[rating[i + 2]])
        #         print((rating[i], rating[i+1], rating[i+2]))
        #         cnt += 1
        
        
        
                
                
        
        # for i in range(len(rating)-1, 1, -1):
        #     if dic[rating[i]] > dic[rating[i -1]] and dic[rating[i - 1]] > dic[rating[i -2]]:
        #         print(dic[rating[i]], dic[rating[i - 1]], dic[rating[i - 2]])
        #         print((rating[i], rating[i-1], rating[i-2]))
        #         cnt += 1
                
        return cnt                                                            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count_teams = 0
        temp_team = []
        all_possible_teams = []
        for i in range(len(rating)):
            
            for j in range(i, len(rating)):
                
                
                for k in range(j, len(rating)):
                    
                    if i != j and j != k:
                        all_possible_teams.append((rating[i], rating[j], rating[k]))
                        
        
        for i in all_possible_teams:
            if i[0] < i[1] and i[1] < i[2]:
                count_teams = count_teams + 1
            if i[0] > i[1] and i[1] > i[2]:
                count_teams = count_teams + 1
        return count_teams
        
            


class Solution:
    def choose_inc(self,idx, num, gt, stack):
        if num == 0:
            self.soln.add(tuple(stack))
            return
        for jidx in range(idx, len(self.rating)):
            jnum = self.rating[jidx]
            #print(jidx, jnum, jnum> gt)
            if jnum > gt:
                self.choose_inc(jidx+1, num -1, jnum, stack + [jnum])
    
    def numTeams(self, rating: List[int]) -> int:
        self.soln = set()
        self.rating = rating
        self.choose_inc(0, 3, 0, [])
        sol_fwd = list(self.soln)
        self.soln = set()
        self.rating.reverse()
        self.choose_inc(0,3,0,[])
        return len(sol_fwd) + len(self.soln)

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = []
        for i in range(len(rating)):
            for j in range(len(rating)):
                for k in range(len(rating)):
                    if i<j<k and (rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]):
                        result.append(rating)
        return len(result)


class Solution:
    def numTeams(self, rating: List[int]) -> int:
#         target=3
#         self.count=0
#         self.lst=[]
#         def isSolution(candidate_count,candid):
#             if candidate_count==target and ((candid[0]<candid[1]<candid[2]) or (candid[0]>candid[1]>candid[2])):
#                 return True
#             # if candidate_count==target:return False
            
#         def backtrack(index,rating,candidates,candidate_count):
#             if isSolution(candidate_count,candidates):
#                 self.count+=1
#                 return 
#             if candidate_count<3:
#                 for i in range(index,len(rating)):
#                     candidates.append(rating[i])
#                     backtrack(i+1,rating,candidates,candidate_count+1)
#                     candidates.pop()
        
#         directions=[1,-1]
#         #-1 means decreasing order
#         # for direction in directions:
#         backtrack(0,rating,[],0)
#         # return len(self.lst)
#         return self.count
        
        
        
        
        target=3
        self.count=0
        self.lst=[]
        def isSolution(candidate_count):
            if candidate_count==target:
                return True
            
        def isViable(rating,i,candidates,candidate_count,direction):
            if i==0 or candidate_count==0:return True
            
            if direction==-1 and rating[i]<candidates[-1]:
                return True
            if direction==1 and rating[i]>candidates[-1]:
                return True
            return False
            
            
        def backtrack(index,rating,candidates,candidate_count,direction):
            if isSolution(candidate_count):
                self.count+=1
                return 
            if candidate_count<3:
                for i in range(index,len(rating)):
                    if isViable(rating,i,candidates,candidate_count,direction):
                        candidates.append(rating[i])
                        backtrack(i+1,rating,candidates,candidate_count+1,direction)
                        candidates.pop()
        
        directions=[1,-1]
        #-1 means decreasing order
        for direction in directions:
            backtrack(0,rating,[],0,direction)
        # return len(self.lst)
        return self.count
                
                
                
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        
        def dfs(i: int, prefix: List[int], increasing: bool) -> int:
            if len(prefix) == 3: return 1
            if i == len(rating): return 0
            result = 0
            rate = rating[i]
            if (increasing and prefix[-1] < rate) or (not increasing and prefix[-1] > rate):
                result += dfs(i+1, prefix + [rate], increasing)
            result += dfs(i+1, prefix, increasing)
            return result

        
        result = 0
        for i in range(len(rating)):
            result += dfs(i + 1, [rating[i]], True) + dfs(i + 1, [rating[i]], False)
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i, s1 in enumerate(rating[:-2]):
            for j, s2 in enumerate(rating[i+1:-1]):
                if s2 > s1:
                    for s3 in rating[i+j+2:]:
                        if s3 > s2:
                            count += 1
                else:
                    for s3 in rating[i+j+2:]:
                        if s3 < s2:
                            count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        output = 0
        for i in range(len(rating)):
            for j in range(len(rating)):
                if i >= j:
                    continue
                for k in range(len(rating)):
                    if j >= k:
                        continue
                    if rating[i] > rating[j] > rating[k] or rating[i] < rating[j] < rating[k]:
                        output += 1
        return output                


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        target=3
        self.count=0
        self.lst=[]
        def isSolution(candidate_count):
            if candidate_count==target:
                return True
            
        def isViable(rating,i,candidates,candidate_count,direction):
            if i==0 or candidate_count==0:return True
            
            if direction==-1 and rating[i]<candidates[-1]:
                return True
            if direction==1 and rating[i]>candidates[-1]:
                return True
            return False
            
            
        def backtrack(index,rating,candidates,candidate_count,direction):
            if isSolution(candidate_count):
                self.count+=1
                return 
             
            for i in range(index,len(rating)):
                if isViable(rating,i,candidates,candidate_count,direction):
                    candidates.append(rating[i])
                    backtrack(i+1,rating,candidates,candidate_count+1,direction)
                    candidates.pop()
        
        directions=[1,-1]
        #-1 means decreasing order
        for direction in directions:
            backtrack(0,rating,[],0,direction)
        # return len(self.lst)
        return self.count
                
                
                
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
#         target=3
#         self.count=0
#         self.lst=[]
#         def isSolution(candidate_count,candid):
#             if candidate_count==target and ((candid[0]<candid[1]<candid[2]) or (candid[0]>candid[1]>candid[2])):
#                 return True
#             # if candidate_count==target:return False
            
#         def backtrack(index,rating,candidates,candidate_count):
#             if isSolution(candidate_count,candidates):
#                 self.count+=1
#                 return 
#             if candidate_count<3:
#                 for i in range(index,len(rating)):
#                     candidates.append(rating[i])
#                     backtrack(i+1,rating,candidates,candidate_count+1)
#                     candidates.pop()
        
#         directions=[1,-1]
#         #-1 means decreasing order
#         # for direction in directions:
#         backtrack(0,rating,[],0)
#         # return len(self.lst)
#         return self.count
        
        
        
        
        target=3
        self.count=0
        self.lst=[]
        def isSolution(candidate_count):
            if candidate_count==target:
                return True
            
        def isViable(rating,i,candidates,candidate_count,direction):
            if i==0 or candidate_count==0:return True
            
            if direction==-1 and rating[i]<candidates[-1]:
                return True
            if direction==1 and rating[i]>candidates[-1]:
                return True
            return False
            
            
        def backtrack(index,rating,candidates,candidate_count,direction):
            if isSolution(candidate_count):
                self.count+=1
                return 
             
            for i in range(index,len(rating)):
                if isViable(rating,i,candidates,candidate_count,direction):
                    candidates.append(rating[i])
                    backtrack(i+1,rating,candidates,candidate_count+1,direction)
                    candidates.pop()
        
        directions=[1,-1]
        #-1 means decreasing order
        for direction in directions:
            backtrack(0,rating,[],0,direction)
        # return len(self.lst)
        return self.count
                
                
                
            


class Solution:
    def numTeams(self, a: List[int]) -> int:
        
        def rec(a, start, path, res):
                        
            for i in range(start, len(a)):
                
                if len(path) == 0:
                    path.append(a[i])
                    rec(a, i + 1, path, res)
                    path.pop()
                    
                elif len(path) == 1:
                    if a[i] != path[-1]:
                        path.append(a[i])
                        rec(a, i + 1, path, res)
                        path.pop()
                                                                                
                elif len(path) == 2:
                    if path[0] < path[1] and path[1] < a[i]:
                        path.append(a[i])
                        res.append(path[:])
                        path.pop()
                        
                    elif path[0] > path[1] and path[1] > a[i]:
                        path.append(a[i])
                        res.append(path[:])
                        path.pop()
                        
            return
        
        res = []
        rec(a, 0, [], res)
        
        return len(res)
                        
                    
                
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # return sum(1 for i in range(len(rating)) for j in range(i) for k in range(j) if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k])

        max_rating = 100000

        def strictly_monotonic(
            rating: List[int],
            previous_rating: int,
            remaining_ratings: int,
            ascending: bool,
        ) -> int:
            if not remaining_ratings:
                return 1
            if not rating:
                return 0
            if ascending ^ (rating[0] < previous_rating):
                return strictly_monotonic(
                    rating[1:], rating[0], remaining_ratings - 1, ascending
                ) + strictly_monotonic(
                    rating[1:], previous_rating, remaining_ratings, ascending
                )
            else:
                return strictly_monotonic(
                    rating[1:], previous_rating, remaining_ratings, ascending
                )

        return strictly_monotonic(rating, 0, 3, ascending=True) + strictly_monotonic(
            rating, max_rating + 1, 3, ascending=False
        )


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        target=3
        self.count=0
        self.lst=[]
        def isSolution(candidate_count):
            if candidate_count==target:
                return True
            
        def isViable(rating,i,candidates,direction):
            if i==0 or len(candidates)==0:return True
            
            if direction==-1 and rating[i]<candidates[-1]:
                return True
            if direction==1 and rating[i]>candidates[-1]:
                return True
            return False
            
            
        def backtrack(index,rating,candidates,candidate_count,direction):
            if isSolution(candidate_count):
                # self.lst.append(list(candidates))
                self.count+=1
                return 
             #-1 means decreasing order
            # for direction in directions:
            for i in range(index,len(rating)):
                if isViable(rating,i,candidates,direction):
                    candidates.append(rating[i])
                    backtrack(i+1,rating,candidates,candidate_count+1,direction)
                    candidates.pop()
        
        directions=[1,-1]
        for direction in directions:
            backtrack(0,rating,[],0,direction)
        # return len(self.lst)
        return self.count
                
                
                
            


class Solution:
    def numTeams(self, rating):
        self.count = 0
        def dfs(soldier, idx):
            if len(soldier) == 3:
                if soldier[0] < soldier[1] < soldier[2] or soldier[0] > soldier[1] > soldier[2]:
                    self.count += 1
                return
                # 5 % 3
            for i in range(idx, len(rating)):
                soldier.append(rating[i])
                dfs(soldier, i + 1)
                soldier.pop()
        dfs([],0)
        return self.count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) < 3:
            return 0
        
        teams = []
        self.select([], 3, True, rating, teams)
        self.select([], 3, False, rating, teams)
        
        return len(teams)
        
        
        
    def select(self, choice, length, increasing, ratings, teams):
        if len(choice) == length:
            teams.append(list(choice))
            return True
        
        for i, team in enumerate(ratings):
            selected = None
            if len(choice) == 0:
                selected = team
            elif increasing and choice[-1] < team:
                selected = team
            elif not increasing and choice[-1] > team:
                selected = team
                
            if selected == None:
                continue
                
            choice.append(selected)
            res = self.select(choice, length, increasing, ratings[i + 1:], teams)
            choice.pop()
                
        return False

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for a, soldier_1 in enumerate(rating):
            for b, soldier_2 in enumerate(rating):
                for c, soldier_3 in enumerate(rating):
                    if a < b < c:
                        if soldier_1 < soldier_2 < soldier_3:
                            count += 1
                        if soldier_1 > soldier_2 > soldier_3:
                            count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        for i in range(len(rating) - 2) :
            head = rating[i]
            #print(head)
            for j in range(len(rating) - i - 2) :
                sec = rating[i + j + 1]
                #print(head,sec)
                if sec > head :
                    for k in rating[i + j + 2::] :
                        if k > sec : ans = ans + 1
                elif sec < head : 
                    for k in rating[i + j + 2::] :
                        if k < sec : ans = ans + 1
        return ans

from itertools import combinations
class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        ### Store the index in dictionary 
        from itertools import combinations

        dic = {}
        for i, x in enumerate(rating):
            dic[x] = i
        rating.sort()
        cnt = 0
        combinations = list(combinations(rating,3))

        for comb in combinations:
            if (dic[comb[0]] < dic[comb[1]] and dic[comb[1]] < dic[comb[2]]) or (dic[comb[0]] > dic[comb[1]] and dic[comb[1]] > dic[comb[2]]):
                
                cnt += 1
        return cnt
    
    
    
        # for i in range(len(rating)-2):
        #     print(dic[rating[i]], dic[rating[i + 1]], dic[rating[i + 2]])
        #     if dic[rating[i]] < dic[rating[i + 1]] and dic[rating[i + 1]] < dic[rating[i+ 2]]:
        #         print(dic[rating[i]], dic[rating[i + 1]], dic[rating[i + 2]])
        #         print((rating[i], rating[i+1], rating[i+2]))
        #         cnt += 1
        
        
        
                
                
        
        # for i in range(len(rating)-1, 1, -1):
        #     if dic[rating[i]] > dic[rating[i -1]] and dic[rating[i - 1]] > dic[rating[i -2]]:
        #         print(dic[rating[i]], dic[rating[i - 1]], dic[rating[i - 2]])
        #         print((rating[i], rating[i-1], rating[i-2]))
        #         cnt += 1
                
        return cnt                                                            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0;
        for i in range(0,len(rating)):
            for j in range(1,len(rating)):
                for k in range(2,len(rating)):
                    if (j>i and k>j) and ((rating[i]<rating[j] and rating[j]<rating[k]) or (rating[i]>rating[j] and rating[i]>rating[k] and rating[j]>rating[k])):
                        count=count+1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        target=3
        self.count=0
        self.lst=[]
        def isSolution(candidate_count):
            if candidate_count==target:
                return True
            
        def isViable(rating,i,candidates,direction):
            if i==0 or len(candidates)==0:return True
            
            if direction==-1 and rating[i]<candidates[-1]:
                return True
            if direction==1 and rating[i]>candidates[-1]:
                return True
            return False
            
            
        def backtrack(index,rating,candidates,candidate_count,direction):
            if isSolution(candidate_count):
                # self.lst.append(list(candidates))
                self.count+=1
                return 
             #-1 means decreasing order
            # for direction in directions:
            for i in range(index,len(rating)):
                if isViable(rating,i,candidates,direction):
                    candidates.append(rating[i])
                    backtrack(i+1,rating,candidates,candidate_count+1,direction)
                    candidates.pop()
        
        directions=[1,-1]
        for direction in directions:
            backtrack(0,rating,[],0,direction)
        # return len(self.lst)
        return self.count
        print((self.count))
                
                
                
            


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        l = len(rating)
        for i in range(0, l - 2):
            right = [x for x in rating[i+1:] if x > rating[i]]
            res += sum([len([x for x in right[i+1:] if x > right[i]]) for i in range(len(right))])
            right = [x for x in rating[i+1:] if x < rating[i]]
            res += sum([len([x for x in right[i+1:] if x < right[i]]) for i in range(len(right))])

        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        m_counter = 0
        for index, v1 in enumerate(rating):
            for jdex, v2 in enumerate(rating[index+1:]):
                if v1 < v2:
                    m_counter = m_counter + len([k for k in rating[jdex+index+1:] if k > v2])
                else:
                    m_counter = m_counter + len([k for k in rating[jdex+index+1:] if k < v2])
                print(m_counter)
        return m_counter

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(len(rating)):
                #Never need to check last 2
                #check for 3rd value
                if j <= i:
                    continue
                if rating[i] > rating[j]:
                    for k in rating[j:]:
                        if rating[j] > k:
                            count += 1
                elif rating[i] < rating[j]:
                    for k in rating[j:]:
                        if rating[j] < k:
                            count += 1
                           
        return count
                        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(len(rating) - 2):
            for j in range(i + 1, len(rating) - 1):
                if rating[j] > rating[i]:
                    cnt += len([k for k in rating[j+1:len(rating)] if k > rating[j]])
                if rating[j] < rating[i]:
                    cnt += len([k for k in rating[j+1:len(rating)] if k < rating[j]])
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i, r_i in enumerate(rating):
            for j, r_j in enumerate(rating[i+1:], i+1):
                if r_i == r_j:
                    continue

                if r_i < r_j:
                    count += sum(r_j < r_k for r_k in rating[j+1:])
                else:
                    count += sum(r_j > r_k for r_k in rating[j+1:])
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if not(rating): return 0
        
        asc, desc = 0, 0
        for index in range(len(rating)):
            lrd, lri, rld, rli = 0, 0, 0, 0
            for num in rating[:index]:
                if num<rating[index]:
                    lri += 1
                elif num>rating[index]:
                    lrd += 1
            
            for num in rating[index:]:
                if num>rating[index]:
                    rli += 1
                elif num<rating[index]:
                    rld += 1            
            
            asc += lri * rli
            desc += lrd * rld
        
        return asc+desc


def increasecheck(List,second_index):
    count=0
    for i in List[second_index+1:]:
        if i>List[second_index]:
            
            count+=1
    return count
def decreasecheck(List,second_index):
    count=0
    for i in List[second_index+1:]:
        if i<List[second_index]:
            
            count+=1
    return count
class Solution:
    
    def numTeams(self, rating: List[int]) -> int:
        n=len(rating)
        output=0
        for i in range(n):
            for j in range(n-1):
                if i>j:
                    continue
                if rating[i]>rating[j]:
                    
                    output+=decreasecheck(rating,j)
                    
                if rating[i]<rating[j]:
                    output+=increasecheck(rating,j)
        return output


class Solution:
    def numTeams(self, rating: List[int]) -> int:        
        num_teams = 0
        for i, first_rank in enumerate(rating):
            rest = rating[i+1:]
            for j, second_rank in enumerate(rest):
                if second_rank > first_rank:
                    for k, third_rank in enumerate(rest[j+1:]):
                        if third_rank > second_rank:
                            num_teams += 1
                if second_rank < first_rank:
                    for k, third_rank in enumerate(rest[j+1:]):
                        if third_rank < second_rank:
                            num_teams += 1
        
        return num_teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        l = len(rating)
        res = 0
        for i,r1 in enumerate(rating[:l-2]):
            for j in range(i+1,l-1):
                r2 = rating[j]
                if r1 > r2:
                    for k in range(j+1,l):
                        r3 = rating[k]
                        if r2 > r3:
                            res += 1
                if r1 < r2:
                    for k in range(j+1,l):
                        r3 = rating[k]
                        if r2 < r3:
                            res += 1
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i,x in enumerate(rating):
            for j,y in enumerate(rating[i+1:],i+1):
                if y > x: 
                    #print(f'i: {i}, j: {j}')
                    cnt += sum(z>y for z in rating[j+1:])           
                if y < x:
                    #print(f'i: {i}, j: {j}')
                    cnt += sum(z<y for z in rating[j+1:])    
        return cnt


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        for i in range(len(rating)):
            for j in range(i + 1, len(rating) - 1):
                if rating[i] < rating[j]:
                    for k in range (j , len(rating)):
                        if rating[j] < rating[k]:
                            res += 1
                else:
                    for k in range(j, len(rating)):
                        if rating[j] > rating[k]:
                            res +=1
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i + 1, len(rating)):
                if rating[i] < rating[j]:
                    for k in range(j + 1, len(rating)):
                        if rating[j] < rating[k]:
                            count += 1
                if rating[i] > rating[j]:
                    for k in range(j + 1, len(rating)):
                        if rating[j] > rating[k]:
                            count += 1
        return count



class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i,x in enumerate(rating):
            for j,y in enumerate(rating[i+1:],i+1):
                if y > x: 
                    cnt += sum(z>y for z in rating[j+1:])           
                if y < x:
                    cnt += sum(z<y for z in rating[j+1:])    
        return cnt


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res=0
        record = []
        #rec = []
        for i in range(0,len(rating)):
            record.append([])
            for j in range(i+1):
                record[i].append(None)
            for j in range(i+1,len(rating)):
                if rating[j] > rating[i]:
                    record[i].append(True)
                elif rating[j] < rating[i]:
                    record[i].append(False)
        for i in range(0,len(rating)-1):

            for j in range(i+1,len(rating)):
                if record[i][j]:
                    for k in range(j+1,len(rating)):
                        if record[j][k]:
                            res += 1
                            #rec.append((rating[i],rating[j],rating[k]))
                elif record[i][j]==False:
                    for k in range(j+1,len(rating)):
                        if record[j][k]==False:
                            res += 1
                            #rec.append((rating[i], rating[j], rating[k]))
        
        return res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        a = 0
        
        while a < len(rating) - 2:
            b = a+1
            while b < len(rating) - 1:
                c = b+1
                if rating[a] < rating[b]:
                    for c in range(c, len(rating)):
                        if rating[b] < rating[c]:
                            teams+=1
                if rating[a] > rating[b]:
                    for c in range(c, len(rating)):
                        if rating[b] > rating[c]:
                            teams+=1
                b+=1
            a+=1
            
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        up = [0]*n
        down = [0]*n
        teams = 0
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if rating[i]<rating[j]:
                    up[i] +=1
                    teams += up[j]
                else:
                    down[i] +=1
                    teams+= down[j]
        return teams

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i in range(len(rating)):
            for j in range(i+1, len(rating)):
                if rating[j] > rating[i]:
                    for k in range(j+1, len(rating)):
                        if rating[k] > rating[j]:
                            count += 1
                elif rating[i] > rating[j]:
                    for k in range(j+1, len(rating)):
                        if rating[k] < rating[j]:
                            count += 1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # Brute force O(n**3)
        res = 0
        for i in range(len(rating) - 2):
            for j in range(i+1,len(rating) - 1):
                if rating[j] < rating[i]:
                    # Check for increasing
                    for k in range(j+1,len(rating)):
                        if rating[k] < rating[j]:
                            res += 1
                else:
                    for k in range(j+1,len(rating)):
                        if rating[k] > rating[j]:
                            res += 1
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) > 2:
            count = 0
            D = {}
            for i in range(len(rating)):
                for j in range(i + 1, len(rating)):
                    if rating[i] < rating[j]:
                        for k in range(j + 1, len(rating)):
                            if rating[j] < rating[k]:
                                count += 1
                    elif rating[i] > rating[j]:
                        for k in range(j + 1, len(rating)):
                            if rating[j] > rating[k]:
                                count += 1
            return count
        return 0

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # brute force
        length = len(rating)
        ans = 0

        for i in range(length-2):
            temp = rating[i]

            for j in range(i+1, length):
                if rating[j] > temp:
                    for k in range(j+1, length):
                        if rating[k] > rating[j]:
                            ans += 1

                if rating[j] < temp:
                    for k in range(j+1, length):
                        if rating[k] < rating[j]:
                            ans += 1

        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        num_teams = 0
        for i in range(len(rating) - 2):
            for j in range(i + 1, len(rating)- 1):
                if rating[i] < rating[j]:
                    for k in range(j + 1, len(rating)):
                        if rating[j] < rating[k]:
                            num_teams += 1
                elif rating[i] > rating[j]:
                    for k in range(j + 1, len(rating)):
                        if rating[j] > rating[k]:
                            num_teams += 1
        return num_teams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)-1):
                if(rating[j]>rating[i]):
                    for k in range(j+1,len(rating)):
                        if(rating[k]>rating[j]):
                            count=count+1
                else:
                    for k in range(j+1,len(rating)):
                        if(rating[k]<rating[j]):
                            count=count+1
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result=0
        if len(rating)<3:
            result=0
            return result
        
        for i in range(1, len(rating)-1):
            
            # from small to large
            for j in range(0,i):
                if(rating[j]<rating[i]):
                    for k in range(i+1, len(rating)):
                        if rating[i]<rating[k]:
                            result+=1
            
            
            # from large to small
            for j in range(0,i):
                if(rating[j]>rating[i]):
                    for k in range(i+1, len(rating)):
                        if rating[i]>rating[k]:
                            result+=1
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        res = 0
        
        for p in range(n - 2):
            for q in range(p + 1, n - 1):
                    if rating[p] > rating[q]:
                        for o in range(q + 1, n):
                            if rating[q] > rating[o]:
                                res += 1
        
        for p in range(n - 2):
            for q in range(p + 1, n - 1):
                    if rating[p] < rating[q]:
                        for o in range(q + 1, n):
                            if rating[q] < rating[o]:
                                res += 1
        return res


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        n = len(rating)
        for i in range(n):
            for j in range(i+1, n):
                if rating[j] > rating[i]:
                    for k in range(j+1, n):
                        if rating[k] > rating[j]:
                            result += 1
        for i in range(n):
            for j in range(i+1, n):
                if rating[j] < rating[i]:
                    for k in range(j+1, n):
                        if rating[k] < rating[j]:
                            result += 1
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cpt = 0
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                if rating[j]>rating[i]:
                    for k in range(j+1,len(rating)):
                        if rating[k]>rating[j]:
                            cpt += 1
        rating.reverse()
        for i in range(len(rating)):
            for j in range(i+1,len(rating)):
                if rating[j]>rating[i]:
                    for k in range(j+1,len(rating)):
                        if rating[k]>rating[j]:
                            cpt += 1
        return cpt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        L = len(rating)
        result = 0
        
        for i in range(1, L - 1):
            pivot = rating[i]
            loL, hiL, loR, hiR = 0, 0, 0, 0
            for j in range(i):
                if rating[j] > pivot:
                    hiL +=1
                else:
                    loL += 1
            for j in range(i+1, L):
                if rating[j] > pivot:
                    hiR +=1
                else:
                    loR += 1
            result += loL * hiR + loR * hiL
            
        return result


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        return self.numTeams_brute_force(rating)
    
    # O(n^3) time and O(1) space solution
    def numTeams_brute_force(self, rating):
        n = 0
        for i in range(len(rating)):
            for j in range(i + 1, len(rating)):
                if rating[j] < rating[i]:
                    for k in range(j + 1, len(rating)):
                        if rating[k] < rating[j]:
                            n += 1
                else:
                    for k in range(j + 1, len(rating)):
                        if rating[k] > rating[j]:
                            n += 1
        return  n

class Solution:
    def numTeams(self, rating: List[int]) -> int:
#         lis = []
#         for i in range(0, len(rating)):
#             lis.append(i, rating[i])
            
#         lis.sort(key = lambda x : x[1])
        
        count = 0
        
        for i in range(0, len(rating)):
            for j in range(i+1, len(rating)):
                if rating[i] >= rating[j]:
                    continue
                for k in range(j+1, len(rating)):
                    if rating[j] < rating[k]:
                        count += 1
        
        for i in range(0, len(rating)):
            for j in range(i+1, len(rating)):
                if rating[i] <= rating[j]:
                    continue
                for k in range(j+1, len(rating)):
                    if rating[j] > rating[k]:
                        count += 1
        
        return count
        
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        y, x, ans = 0, 0, 0
        for i in rating[:-2]:
            for j in rating[x+1:-1]:
                for k in rating[y+2:]:
                    if i < j < k or i > j > k:                  
                        ans += 1
                y += 1
            x += 1
            y = x
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        output = 0
        
        for k in range(len(rating)-2):
            for j in range(k+1 , len(rating)-1):
                if (rating[j] > rating[k]):
                    for i in range(j+1 , len(rating)):
                        if (rating[i] > rating[j]):
                            output += 1
                if (rating[j] < rating[k]):
                    for i in range(j+1 , len(rating)):
                        if (rating[i] < rating[j]):
                            output += 1
                            
        return output

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        import itertools
        return len([1 for i,j,k in itertools.combinations(rating,3) if i<j<k or i>j>k])

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        ans = 0
        for i in range(n):
            for j in range(i+1,n):
                if rating[j] > rating[i]:
                    direction = 1
                else:
                    direction = 0
                for k in range(j+1,n):
                    if direction and rating[k] > rating[j]: 
                        ans += 1
                    if not direction and rating[k] < rating[j]: 
                        ans += 1
        return ans


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        less = {}
        more = {}
        count = []
        n = len(rating)
        for i in range(n):
            l = []
            m = []
            for j in range(i+1,n):
                if(rating[i]<rating[j]):
                    l.append(rating[j])
                if(rating[i]>rating[j]):
                    m.append(rating[j])
            if(len(l)>0):
                less[rating[i]] = l
            if(len(m)>0):
                more[rating[i]] = m
        print((less,more))
        for i in list(less.keys()):
            t = less[i]
            for j in t:
                if(j in list(less.keys())):
                        for k in less[j]:
                            count.append([i,j,k])
        for i in list(more.keys()):
            t = more[i]
            for j in t:
                if(j in list(more.keys())):
                        for k in more[j]:
                            count.append([i,j,k])
        return(len(count))


class Solution:
    def __init__(self):
        self.num_teams = 0
        
    def numTeams(self, rating: List[int]) -> int:      
        for i in range(len(rating)):
            first_soldier = rating[i]
            self.compareFirstSoldier(first_soldier, rating[i:])
        
        reversed_rating = rating
        reversed_rating.reverse()
        for i in range(len(reversed_rating)):
            first_soldier = reversed_rating[i]
            self.compareFirstSoldier(first_soldier, reversed_rating[i:])
            
        return self.num_teams
                
            
    def compareFirstSoldier(self, soldier_val: int, rating: List[int]) -> None:
        for j in range(len(rating)):
            if soldier_val < rating[j]:
                second_soldier = rating[j]
                self.compareSecondSoldier(second_soldier, rating[j:])
    
    def compareSecondSoldier(self, soldier_val: int, rating: List[int]) -> None:
        for k in range(len(rating)):
            if soldier_val < rating[k]:
                self.num_teams += 1
        


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = len(rating)
        if count < 3:
            return 0
        result = 0
        for i in range(count-2):
            for j in range(i+1, count-1):
                increasing = rating[j] > rating[i]
                for k in range(j+1, count):
                    if increasing and rating[k] > rating[j]:
                        result += 1
                    elif not increasing and rating[k] < rating[j]:
                        result += 1
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(1, len(rating) - 1):
            s_l = 0
            s_r = 0
            l_l = 0
            l_r = 0
            for j in range(0, i):
                if rating[j] < rating[i]:
                    s_l += 1
                elif rating[j] > rating[i]:
                    l_l += 1
            for k in range(i+1, len(rating)):
                if rating[k] > rating[i]:
                    s_r += 1
                elif rating[k] < rating[i]:
                    l_r += 1
            cnt += s_l * s_r + l_l * l_r
        return cnt

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        result = 0
        for i in range(len(rating)):
            for j in range(i + 1, len(rating)):
                if rating[j] == rating[i]:
                    continue
                if rating[j] < rating[i]:
                    result += sum(num < rating[j] for num in rating[j+1:])
                else:
                    result += sum(num > rating[j] for num in rating[j+1:])
        return result

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        answer = 0
        is_increasing = False
        for i in range(len(rating)-2):
            for j in range(i+1, len(rating)-1):
                if rating[i] == rating[j]:
                    continue

                is_increasing = rating[i] < rating[j]
                for k in range(j+1, len(rating)):
                    if is_increasing and rating[j] < rating[k]:
                        answer += 1
                    elif not is_increasing and rating[j] > rating[k]:
                        answer += 1

        return answer

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        teams = 0
        for i1 in range(len(rating) - 2):
            for i2 in range(i1 + 1, len(rating) - 1):
                if rating[i1] < rating[i2]:
                    for i3 in range(i2 + 1, len(rating)):
                        teams += rating[i2] < rating[i3]
                elif rating[i1] > rating[i2]:
                    for i3 in range(i2 + 1, len(rating)):
                        teams += rating[i2] > rating[i3]
        
        return teams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        for i, r_i in enumerate(rating):
            for j, r_j in enumerate(rating[i+1:], i+1):
                if r_i == r_j:
                    continue

                if r_i < r_j:
                    count += sum(r_j < r_k for r_k in rating[j+1:])
                else:
                    count += sum(r_j > r_k for r_k in rating[j+1:])

        return count


from functools import lru_cache
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        a = rating
        @lru_cache()
        def helper(curr, left):
            if left == 0: return 1
            if curr == len(a): return 0
            
            return sum([helper(i, left-1) for i in range(curr+1, len(a)) if a[i] > a[curr]] +[0])
        
        res = sum([helper(i, 2) for i in range(len(a))]+[0])
        helper.cache_clear()
        a = a[::-1]
        res += sum([helper(i, 2) for i in range(len(a))]+[0])
        return res

from functools import lru_cache

@lru_cache
def find_ns( rating, i, n, bigger ):
    res = []
    while i < len( rating ):
        if bigger and rating[i] > n or not bigger and rating[i] < n:
            res.append( i )
        i += 1
    return res
        

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        rating = tuple( rating )
        i = 0
        num_teams = 0
        while i < len(rating)-2:
            for i2 in find_ns( rating, i+1, rating[i], True ):
                for i3 in find_ns( rating, i2+1, rating[i2], True ):
                    num_teams += 1
            for i2 in find_ns( rating, i+1, rating[i], False ):
                for i3 in find_ns( rating, i2+1, rating[i2], False ):
                    num_teams += 1
            i += 1
        return num_teams


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count=0
        for i in range(0,len(rating)-2):
            for j in range(i+1,len(rating)):
                flag=0
                if rating[j]>rating[i]:
                    flag=1
                else:
                    flag=0
                for k in range(j+1,len(rating)):
                    if flag==1:
                        if rating[k]>rating[j]:
                            count=count+1
                    else:
                        if rating[k]<rating[j]:
                            count=count+1
        return count
                        
                    


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        cnt = 0
        for i in range(len(rating)-2):
            for j in range(i+1,len(rating)):
                if rating[i]<rating[j]:
                    for k in range(j+1,len(rating)):
                        if rating[j]<rating[k]:
                            cnt+=1
                if rating[i]>rating[j]:
                    for k in range(j+1,len(rating)):
                        if rating[j]>rating[k]:
                            cnt+=1
        return  cnt

class Solution:
    def numTeams(self, rating: list) -> int:
        left_less, left_greater = 0, 0
        right_less, right_greater = 0, 0
        count = 0
        for j in range(len(rating)):
            for i in range(j):
                if rating[i] < rating[j]:
                    left_less += 1
                elif rating[i] > rating[j]:
                    left_greater += 1
            for k in range(j+1, len(rating)):
                if rating[j] < rating[k]:
                    right_greater += 1
                elif rating[j] > rating[k]:
                    right_less += 1
            count += left_less * right_greater + left_greater * right_less
            left_less = left_greater = right_less = right_greater = 0
        return count

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans = 0
        for i, j, k in combinations(rating, 3):
            if i < j < k or i > j > k:
                ans += 1
        return ans

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        import itertools
        return len([1 for i,j,k in itertools.combinations(rating,3) if i<j<k or i>j>k])                

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n=len(rating)
        teams=0
        for i in range(n):
            for k in range(i+2,n):
                if rating[i]<rating[k]:
                    teams+=len([r for r in rating[i+1:k] if rating[i]<r<rating[k]])
                else:
                    teams+=len([r for r in rating[i+1:k] if rating[i]>r>rating[k]])
        
        # for i in range(n):
        #     for j in range(i+1,n):
        #         for k in range(j+1,n):
        #             if rating[i]<rating[j]<rating[k] or rating[i] > rating[j] > rating[k]:
        #                 teams+=1
        return teams


class Solution:
    def numTeams(self, ratings: List[int]) -> int:
        ans = 0
        for i in range(len(ratings)-2):
            for j in range(i,len(ratings)-1):
                if ratings[j] > ratings[i]:
                    for k in range(j,len(ratings)):
                        if ratings[k] > ratings[j]:
                            ans += 1
                if ratings[j] < ratings[i]:
                    for k in range(j,len(ratings)):
                        if ratings[k] < ratings[j]:
                            ans += 1
        return ans


def look_for_ascending(t_list, sub_array): 
    good_lists = 0
    for idx in range(0, len(sub_array)):
        if sub_array[idx] > t_list[-1]:
            if len(t_list) ==2:
                good_lists+=1
            else:
                good_lists+= look_for_ascending(t_list+[sub_array[idx]], sub_array[idx+1:])
    
    return good_lists

def look_for_descending(t_list, sub_array): 
    good_lists = 0
    for idx in range(0, len(sub_array)):
        if sub_array[idx] < t_list[-1]:
            if len(t_list) ==2:
                good_lists+=1
            else:
                good_lists+= look_for_descending(t_list+[sub_array[idx]], sub_array[idx+1:])
    
    return good_lists



class Solution:
    def numTeams(self, rating: List[int]) -> int:
        good=0
        for idx in range(len(rating)):
            good+=look_for_ascending([rating[idx]], rating[idx+1:]) + look_for_descending([rating[idx]], rating[idx+1:])
        return good

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        size = len(rating)
        for idx, val in enumerate(rating):
            for next in range(idx+1,size):
                if rating[next] > val:
                    new = next + 1
                    while new < size:
                        if rating[new] > rating[next]:
                            count += 1
                        new += 1
                elif rating[next] < val:
                    new = next + 1
                    while new < size:
                        if rating[new] < rating[next]:
                            count += 1
                        new += 1
        return count


class Solution:
    def numTeams(self, rating: List[int]) -> int:
        if len(rating) <= 2:
            return 0
        res =0
        for i in range(len(rating)-2):
            incs = []
            decs = []
            for j in range(i+1,len(rating)-1):
                if rating[j] > rating[i]:
                    incs.append(j)
                elif rating[j] < rating[i]:
                    decs.append(j)
            for ind in incs:
                for j in range(ind+1,len(rating)):
                    if rating[j] > rating[ind]:
                        res += 1
            for ind in decs:
                for j in range(ind+1,len(rating)):
                    if rating[j] <rating[ind]:
                        res += 1
        return res

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        
        count = 0
        n = len(rating)
        
        for i in range(n-2):
            for j in range(i+1, n-1):
                if rating[i] < rating[j]:
                    for k in range(j+1, n):
                        if rating[k] > rating[j]:
                            count += 1
                elif rating[i] > rating[j]:
                    for k in range(j+1, n):
                        if rating[k] < rating[j]:
                            count += 1
        return count