$\pi^k()$, extending and improving the previous results of Munro [[*et al.*]{}]{} [@MRRR03].

\[thm:runs\] Let $\pi$ be a permutation on $n$ elements that consists of $\rho$ interleaved increasing or decreasing runs. We can store $\pi$ in $2 n H ({\ensuremath{\mathsf{runs}}}(\pi)) + o(n)(H ({\ensuremath{\mathsf{runs}}}(\pi)) + 1)$ bits and perform $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {\lg \lg \rho} \right)}}$ time.

We first replace all the elements of the $r$th run by $r$, for $1\le r\le\rho$. Let $s$ be the resulting string and let $s'$ be $s$ permuted according to $\pi$. We store $s$ and $s'$ using Theorem \[thm:partitioning\]$(i)$ and store $\rho$ bits indicating whether each run is increasing or decreasing. Notice $s' [\pi (i)] = s [i]$ and, if $\pi (i)$ is part of an increasing run, then $s'.{\ensuremath{\mathsf{rank}}}_{s [i]} (\pi (i)) = s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i)$, so $$\pi (i) = s'.{\ensuremath{\mathsf{select}}}_{s [i]} \left( s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i) \right)\,;$$ if $\pi (i)$ is part of a decreasing run, then $s'.{\ensuremath{\mathsf{rank}}}_{s [i]} (\pi (i))
= s.{\ensuremath{\mathsf{rank}}}_{s [i]} (n) +1 - s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i)$, so $$\pi (i) = s'.{\ensuremath{\mathsf{select}}}_{s [i]} \left( s.{\ensuremath{\mathsf{rank}}}_{s [i]} (n) +1 - s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i) \right)\,.$$ A ${\ensuremath{\pi^{-1}}}()$ query is symmetric. The space of the bitmap is $\rho = o(nH({\ensuremath{\mathsf{runs}}}(\pi)))$ because $nH({\ensuremath{\mathsf{runs}}}(\pi)) 