Close entries in large permutations Suppose $n>1$ and choose a permutation $\{1,2,\dots,n\} \rightarrow \{\sigma_1,\sigma_2,\dots,\sigma_n\}$ such that we maximize $\min_{i \not = j} d(i,j) + \log_2|\sigma_j - \sigma_i|$ where we take distances $d(i,j)$ cyclicly, so if $n = 16$ then $d(1,16) = 1$.  Let 
$$C_n = \max_{\sigma_n} \min_{i \not = j} \left\{|d(i,j) + \log_2|\sigma_j - \sigma_i|\right\}$$
For small $n$ this is easily computable.  For example $C_2 = C_3 = C_4$.  The order $1,3,5,2,4$ gives $C_5 = 2$.
It seems like $C_n = \lfloor \log_2 (n-1)\rfloor$.  Is this true?  It seems like it shouldn't be difficult to establish it as a lower bound (assuming I haven't made any dumb mistakes) but showing that it you can't do better with any permutation seems a bit more difficult.

An upper bound can be established by looking at nearest neighbours. Here $d(i,j)=1$, and $|\sigma_j-\sigma_i|\le\left\lfloor\frac n2\right\rfloor$, so $d(i,j)+\log_2|\sigma_j-\sigma_i|\le1+\log_2\left\lfloor\frac n2\right\rfloor\le\log_2n$. Your value $C_n=\left\lfloor\log_2(n-1)\right\rfloor$ seems to be wrong, since for $n=2$ it yields $0$. From computer searches, I get $C_n=1$ up to $n=4$, then $C_n=2$ up to $n=7$, then $C_n=1+\log_23$ up to $n=10$, and $C_{11}=3$.
