def anti_exceedance_positions(x):
    """
    sage: x = DecoratedPermutation([5,4,1,2,7,6,9,-8,3])
    sage: anti_exceedance_positions(x)
    [3, 4, 9, 6]
    """
    pi = x.to_signed_permutation().permutation()
    pi_inv = pi.inverse()
    n = len(pi)
    anti = []
    for i in range(1, n+1):
        if i < pi_inv(i) or x[i-1] == i:
            anti.append(pi_inv(i))
    return anti

def to_grassmann_interval(x):
    """
    sage: x = DecoratedPermutation([5,4,1,2,7,6,9,-8,3])
    sage: to_grassmann_interval(x)
    ([1, 2, 6, 3, 5, 4, 7, 9, 8], [3, 4, 6, 9, 1, 2, 5, 7, 8])
    """
    n = len(x)
    I = anti_exceedance_positions(x)
    u1 = []
    u2 = []
    v1 = []
    v2 = []
    for i in range(1, n+1):
        if i in I:
            v1.append(i)
            u1.append(abs(x[i-1]))
        else:
            v2.append(i)
            u2.append(abs(x[i-1]))
    return Permutation(u1+u2), Permutation(v1+v2)

def interval_size(x):
    u, v = to_grassmann_interval(x)
    return sum(1 for pi in u.bruhat_greater() if pi.bruhat_lequal(v))