static Map<String, Boolean> memo = new HashMap<>();

public static String permutationGame(List<Integer> arr) {
// Write your code here
memo.clear();
return findWinner(arr) ? "Bob" : "Alice";

}

static boolean isIncreasing(List<Integer> arr) {
    for (int i = 0; i < arr.size() - 1; i++) {
        if (arr.get(i) > arr.get(i + 1)) {
            return false;
    }
}
return true;
}

static boolean findWinner(List<Integer> arr) {
    String key = arr.toString();
    if (memo.containsKey(key)) {
        return memo.get(key);
    }
    if (isIncreasing(arr)) {
        memo.put(key, true);
        return true;
    }
    for (int i = 0; i < arr.size(); i++) {
        if (findWinner(Stream.concat(arr.subList(0, i).stream(),
            arr.subList(i+1, arr.size()).stream())
            .collect(Collectors.toList()))) {
        memo.put(key, false);
        return false;
        }
    }
    memo.put(key, true);
    return true;
}

def willWinPermutationGame(tup, memo):
    if len(tup) == 1:
        return False
    
    if memo.get(tup) is not None:
        return memo[tup]
    
    is_increasing = True
    pivot = tup[0]
    for i in range(1, len(tup)):
        if tup[i] < pivot:
            is_increasing = False
            break
        pivot = tup[i]
    if is_increasing:
        memo[tup] = False
        return False
    
    for i in range(len(tup)):
        left = [] if i == 0 else list(tup[:i])
        right = [] if i == len(tup) - 1 else list(tup[i+1:])
        if not willWinPermutationGame(tuple(left + right), memo):
            memo[tup] = True
            return True
    
    return False
    

def permutationGame(arr):
    memo = {}
    return "Alice" if willWinPermutationGame(tuple(arr), memo) else "Bob"

def permutationGame(arr):
    memo = {}

    def winner(nums):
        if tuple(nums) in memo:
            return memo[tuple(nums)]

        if sorted(nums) == nums:
            memo[tuple(nums)] = 'Bob'
            return 'Bob'

        for i in range(len(nums)):
            if winner(nums[:i] + nums[i+1:]) == 'Bob':
                memo[tuple(nums)] = 'Alice'
                return 'Alice'

        memo[tuple(nums)] = 'Bob'
        return 'Bob'

    return winner(arr)

@functools.lru_cache(None)
def PG(arr):
    if list(arr) == sorted(list(arr)):
        return 'Bob' 
    else:
        for i in range(len(arr)):
            if PG(arr[:i]+arr[i+1:]) == 'Bob': 
                return 'Alice'
        return 'Bob'   
    
def permutationGame(arr):
    return PG(tuple(arr))

5 3 2 1 4 (after i get to 4 then below are all a) -> b Bob wins (let's skip those branches)
  3 2 1 4 (if below is b then a, else i ++) (last case b) - > a       
    2 1 4 : a -> 3 1 4: a -> 3 2 4: a -> 3 2 1: b (below all a then this is b)
      1 4 : b      1 4: b      2 4: b      2 1: a -> 3 1: a -> 3 2: a
                                             1: b      1: b      2: b
        */
        //We can see that alot of branches are dupplicated
        //hence the use of MEMORY map, 
        //allowing us to skip their isIncreasing checks