an array containing pointers to every $t$th element in the cycle, which we call ‘marked’. We also store a compressed binary string, aligned to $\pi$, indicating the marked elements. For each marked element, we record to which cycle it belongs and its position in the array of that cycle.

To compute $\pi^k (i)$, we repeatedly apply $\pi()$ at most $t$ times until we either loop (in which case we need apply $\pi()$ at most $t$ more times to find $\pi^k (i)$ in the loop) or we find a marked element. Once we have reached a marked element, we use its array position and cycle length to find the pointer to the last marked element in the cycle before $\pi^k (i)$, and the number of applications of $\pi()$ needed to map that to $\pi^k (i)$ (at most $t$). A $\pi^{- k}$ query is similar (note that it does not need to use ${\ensuremath{\pi^{-1}}}()$).

As an example, given a constant $\epsilon > 0$ and a value $t \leq n$, we can combine Theorems \[thm:contiguous runs\] and \[thm:exponent\] to obtain a data structure that stores Sadakane’s $\Psi$ function [@Sad03] for $s$ in $n H_0 (s) + o (n) (H_0 (s) + 1) + 