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?