# WARNING: takes a long time even for permutations of 5.

def defect_set(sigma, w):
    """
    INPUT:

    - w is a reduced word for a permutation
    - sigma is the mask, given as a binary word of length l(w)

    OUTPUT:
    
    - the defect set, that is the set of positions j such that
    l(w^{\sigma[j-1]} w_j) < l(w^{\sigma[j-1]}) 

    """
    res = []
    S = Permutations(max(w)+1)
    w_S = [S.simple_reflection(e) for e in w]
    w_up_to_j = S([])
    for j in range(len(w)-1):
        if sigma[j] == 1:
            w_up_to_j = w_up_to_j.left_action_product(w_S[j])

        if (w_up_to_j.left_action_product(w_S[j+1])).length() < w_up_to_j.length():
            res += [j+2]
    return res

def statistic(pi):
    """
    sage: statistic(Permutation([4,3,5,2,1]))
    3
    sage: statistic(Permutation([5,4,2,1,3]))
    3
    """
    k = pi.length()
    if not k:
        return 0
    masks = cartesian_product([[0,1]]*k)
    return max([len(defect_set(m, w)) 
                for m in masks
                for w in pi.reduced_words()])