\ge (\rho-1)\lg n$.

We now consider the case of runs restricted to be strictly incrementing ($+1$) or decrementing ($-1$), while still letting them be interleaved: such runs were not directly considered before.

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

Due to space constrains, we leave the proof of this theorem to the appendix.

Notice that, if $\pi$ consists of $\rho$ contiguous increasing or decreasing runs, then ${\ensuremath{\pi^{-1}}}$ consists of $\rho$ interleaved incrementing or decrementing runs. Therefore, Theorem \[thm:strict runs\] applies to such permutations as well, with the time bounds for $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries reversed.

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