HTMLify

import math

class Solution:
    def countBSTs(self, arr):
        n = len(arr)
        
        def get_catalan(k):
            if k == 0 or k == 1:
                return 1
            return math.comb(2 * k, k) // (k + 1)
            
        res = []
        for root_val in arr:
            left_count = 0
            right_count = 0
            
            for x in arr:
                if x < root_val:
                    left_count += 1
                elif x > root_val:
                    right_count += 1
            
            num_bsts = get_catalan(left_count) * get_catalan(right_count)
            res.append(num_bsts)
            
        return res