{1/\epsilon} \right)}}$ time and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {\lg \lg \rho} \right)}}$ time.

If $\pi$’s runs are both contiguous and incrementing or decrementing, then so are the runs of ${\ensuremath{\pi^{-1}}}$. In this case we can store $\pi$ in ${\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}}$ bits and answer $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time. To do this, we use two predecessor data structures: for each run, in one of the data structures we store the position $j$ in $\pi$ of the first element of the run, with $\pi (j)$ as auxiliary information; in the other, we store $\pi (j)$, with $j$ as auxiliary information. To perform a query $\pi (i)$, we use the first predecessor data structure to find the starting position $j$ of the run containing $i$, and return $\pi (j) + i - j$. A ${\ensuremath{\pi^{-1}}}()$ query is symmetric. Decreasing runs are handled as before.

\[thm:contiguous strict runs\] Let $\pi$ be a permutation on $n$ elements that consists of $\rho$ contiguous incrementing or decrementing runs. For any constant $\epsilon >
0$, we can store $\pi$ in ${\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}}$ bits and perform $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {1/\epsilon} \right)}}$ time.

We now show how to achieve 