class Solution {
    public int numTeams(int[] rating) {
        if (rating == null || rating.length < 3) {
            return 0;
        }
        
        return dfs(rating, 0, new ArrayList<Integer>(), true) + dfs(rating, 0, new ArrayList<Integer>(), false);
    }
    
    private int dfs(int[] rating, int current, List<Integer> list, boolean isIncreasing) {        
        if (list.size() == 3) {
            return 1;
        }
        
        int ans = 0;
        for (int i = current; i < rating.length; i++) {
            if (list.size() == 0 || (isIncreasing && rating[i] > list.get(list.size() - 1)) || (!isIncreasing && rating[i] < list.get(list.size() - 1))) {
                
                list.add(rating[i]);
                ans += dfs(rating, i + 1, list, isIncreasing);
                list.remove(list.size() - 1);
            }
        }
        return ans;
    }
}