Show Off!

Prerequisites: Constructive Algorithm, Implementation

At first, as you cannot make $a_1$ or $a_n$ the highest pillar after the arrangment, it's a nice observation that you don't need to increase the height of $a_1$ of $a_n$ in any time. So, $a_2$ needs to be $max(a_1+1,a_2)$ to satisfy the $1^{st}$ property. Similarly, $a_{n-1}$ needs to be $max(a_n+1,a_{n-1})$. So, you can calculate $lcost_i$ as the cost needed to make $a_1, a_2, ..., a_i$ strictly increasing and same goes for $rcost_i$ to make $a_i, a_{i+1}, ..., a_n$ strictly decreasing.

So, we check for each index $i$ to be the highest pillar $h$ after the arrangement if possible. The cost for an index $i$ to satisfy the properties is $lcost_{i-1} + rcost_{i+1} + (h - a_i)$ if $a_i \leq h$, $lcost_{i-1} < h$ and $rcost_{i+1} < h$. You just check all the possibilities and take the minimum.

Time Complexity: O(n)