Given a sequence $a_1, a_2,\dots,a_n$, define the two sequences $$l_i=\max_{1 \leq j < i, a_j \geq a_i} j$$ or $0$ if it does not exist; and $$r_i=\min_{i < j \leq n, a_j > a_i} j$$ or $n+1$ if does not exist.
I want to find a permutation of $1, 2, ..., n$ so that $$\sum_{1 \leq i \leq n} \min(i-l_i,r_i -i)$$ is maximized. How can this be done?
Denote the maximum of your sum by $f(n)$, agree also that $f(0)=0$. If we fix $k$ such that $a_k=n$, then the maximal possible value is $\min(k,n+1-k)+f(k-1)+f(n-k)$. So, we get a recursive formula $$f(n)=\max_{1\leqslant k\leqslant (n+1)/2} k+f(k-1)+f(n-k).$$ Now we may forget about permutations and study this recurrence. Assume that $f(n)$ grows as $c(n+1)\ln(n+1)$ for some yet unknown $c$ and we try to prove that $f(n)\leqslant c(n+1)\ln(n+1)$ by induction (base $n=0$ is ok). Denote $k=\alpha(n+1)$, $\alpha\leqslant 1/2$, this reduces to $\alpha-cH(\alpha)\leqslant 0$ where $H(x)=-x\log(x)-(1-x)\log(1-x)$ is the entropy function. $H$ is concave, thus inequality $H(\alpha)\geqslant \alpha/c$ holds iff it holds for $\alpha=1/2$, $c=\frac1{2\log2}$, so $f(n)\leqslant (n+1)\log_2(n+1)$ and we should insert the maximal value $n$ to the middle of the permutation (if you do so, you get almost equality.)
