Suppose for each integer $n\geq 1$ we have a submonoid $M_n\subset \mathrm{Self}(\{1, \dots, n\})$ of self-maps of $\{1, \dots, n\}$.

Suppose we can decide whether a given self-map is an element of $M_n$ in polynomial time in $n$.

Suppose we can list all elements of $M_n$ in polynomial time in $|M_n|\times n$.

Then consider the problem of deciding whether a given element of $\{1, \dots, n\}$ lies in $M_n(1)$.

How large can its asymptotic worst case time complexity be?