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: MEDIUM
Tags: Dynamic programming

Data structures

Range queries
Skill types: Dynamic programming

Data structures

Range queries

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


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):
					teamCount += getTeams(k - 1, l[1:], l[0], asc)
				teamCount += getTeams(k, l[1:], prev, asc)
				if 0:
					if asc:
						if larger_x | (prev is None):
							teamCount += getTeams(k - 1, l[1:], l[0], asc)
						teamCount += getTeams(k, l[1:], prev, asc)
					else:
						if larger_x == False | (prev is None):
							teamCount += getTeams(k - 1, l[1:], l[0], asc)
						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
		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
				else:
					b = 0
				for k in range(j + 1, len(r)):
					if b == 1 and r[k] < r[j]:
						ct += 1
						continue
					if b == 0 and r[k] > r[j]:
						ct += 1
						continue
		return ct


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:
		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


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
		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
		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
		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:
		combos = 0
		for (index, numba) in enumerate(rating[:-2]):
			for numbay in rating[index + 1:-1]:
				for numbaz in rating[rating.index(numbay) + 1:]:
					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:
		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:
		counter = 0
		while len(rating) > 0:
			r = rating.pop(0)
			counter += countDown(rating, r, 1)
			counter += countUp(rating, r, 1)
		return counter

def 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:
			counter += 1
		elif num > value:
			counter += countUp(rating[i:], num, 2)
	return counter

def 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:
			counter += 1
		elif num < value:
			counter += countDown(rating[i:], num, 2)
	return counter


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
		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:
		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):
					if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]:
						ct += 1
		return ct


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:
		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:

		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, 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


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
		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, 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:
		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, r: List[int]) -> int:
		if len(r) < 3:
			return 0
		teams = 0
		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:
		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:
		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:
		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, 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, 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:
		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, 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)):
					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


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:
		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:
		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:
		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:
		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:
		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:
		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


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, 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


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 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):
			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):
			final.append(rating[i])
			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:
		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


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:
		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:
		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:
		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:
				k = j - 1
				while k > i:
					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


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:
		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 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, 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:
		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:
		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


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:
		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:
		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:
		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
		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
		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


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 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:
		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:
		(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


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:
		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 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):
		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):
		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:
		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
		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:
		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)


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]


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])


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:
		return 1
	elif len(myrating) == 0:
		return 0
	score = 0
	for a in range(len(myrating)):
		if 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:
		answer = 0
		for i in range(len(rating)):
			answer += findmyTeams(rating[i:], [rating[i]], rating[i])
		rating.reverse()
		for i in range(len(rating)):
			answer += findmyTeams(rating[i:], [rating[i]], rating[i])
		return answer


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):
		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:

		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)


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()
			elif 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()
			elif 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)
		return len(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]
		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:
		ratings = [[]]
		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
		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:
		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:
		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:

		def solve(arr, n, k, arr_max):
			if k == 0:
				return 1
			if n == len(arr):
				return 0
			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:
		stack = []
		list1 = []
		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] < rating[k] or rating[i] > rating[j] > rating[k]:
						stack.append(rating[i])
						stack.append(rating[j])
						stack.append(rating[k])
						list1.append(stack)
					stack = []
		return len(list1)


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]):
						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:
		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:
		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)):
			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 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 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:
		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:
		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
			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)
			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:
		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


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:
		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
			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)
			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

	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:

		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:])
				elif 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:

		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:
		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
		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]
			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:
		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]
		for direction in directions:
			backtrack(0, rating, [], 0, direction)
		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:
		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):
		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
			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:
		ans = 0
		for i in range(len(rating) - 2):
			head = rating[i]
			for j in range(len(rating) - i - 2):
				sec = rating[i + j + 1]
				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


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:
		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:
					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:
		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:
		result = 0
		if len(rating) < 3:
			result = 0
			return result
		for i in range(1, len(rating) - 1):
			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
			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:
		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:
		(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:
		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


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
					elif rating[k] < rating[j]:
						count = count + 1
		return count


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:
		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]])
		return teams


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