If a permutation $f$ is not one way, what can we say about $f^{p(n)}$? Consider a permutation $f:\{0,1\}^*\rightarrow \{0,1\}^*$, which is not a one-way function, i.e. there exists an efficient probabilistic adversary $\mathcal{A}$ and some polynomial $q(n)$ such that for infinitely many $n$

\begin{equation}
\mathrm{Pr}[\mathcal{A}(f(x)) = x] &gt; \frac{1}{q(n)},
\end{equation}
where the probability is over the internal randomness of $\mathcal{A}$ and  $x$ drawn uniformly at random from $\{0,1\}^n$.

I would now like to prove that $f^{p(n)}$ is not a one way function, for any polynomial $p(n)$. Is this true for all permutations $f$ which are not one way? 

My intuition was that this would be true, and that one could prove this by showing that $\tilde{\mathcal{A}} = \mathcal{A}^{p(n)}$ is a suitable adversary for $f^{p(n)}$. However, I can't get this to work. Is there a clever way to prove this, or is the statement I am trying to prove actually false?
If a permutation $f$ is not one way, we can not conclude about the one-wayness of $f^{p(n)}$. In fact, even $f^2$ could be one-way, if there are one-way length-preserving permutations that is.

Constructive proof: assume $g:\{0,1\}^*\rightarrow \{0,1\}^*$ is a length-preserving OWP, not invertible starting with rank $m$. Define $f$ from $g$ such that, for any bitstring $x$,

$$\begin{align}f(x\mathbin\|0)&amp;=x\mathbin\|1\\f(x\mathbin\|1)&amp;=g(x)\mathbin\|0\end{align}$$

$f$ is a permutation. It is trivially invertible for half its inputs of any fixed width, thus is not a OWP.

$f^2$ is also a permutation, with

$$\begin{align}f^2(x\mathbin\|0)&amp;=g(x)\mathbin\|0\\f^2(x\mathbin\|1)&amp;=g(x)\mathbin\|1\end{align}$$

An hypothetical algorithm that inverts $f^2$ starting at width $n&gt;m$ could be used to invert $g$ at width $n-1\ge m$. With $g$ being a OWF, there is no such algorithm. Hence $f^2$ is one-way.