Say the array is `A`

. Consider the transformation T A = the array after one turn. Evidently, `T: A[x] -> min(A[x-1], A[x] - 1, A[x+1])`

, where we assume that the array is padded with zeros. (Let's also assume any negative values of the array are replaced by zero for convenience.)

Let's investigate `T^2 A[x]`

. This is:

`min(T A[x-1], T A[x] - 1, T A[x+1])`

`= min(min(A[x-2], A[x-1]-1, A[x]), min(A[x-1], A[x] - 1, A[x+1]) - 1, min(A[x], A[x+1] - 1, A[x+2]))`

`= min(A[x-2], A[x-1] - 1, A[x] - 2, A[x+1] - 1, A[x+2])`

.

We can show by induction or otherwise that:

`T^k A[x] = min_{0 <= j <= k} (A[x ± j] - (k-j) )`

When `T^k A[x]`

is positive, all of these terms are positive, namely `A[x ± j] > k-j`

for all `0 <= j <= k`

. Graphically, A contains a pyramid with heights [1, 2, ..., k, k+1, k, ..., 2, 1], and we want to know the largest pyramid contained in A.

If we can know L(x) = the largest k with up-staircase [1, 2, 3, ..., k] that ends at A[x], and R(x) = the largest k with down-staircase [k, k-1, ..., 2, 1] starting at A[x], then the largest pyramid centered at x will have height min(L(x), R(x)), and we can find the maximum over all x. Finding R is similar to finding L, so let's just focus on finding L.

Say L(x) = k, and let's figure out what L(x+1) is.

- If A[x] >= k+1, L(x+1) is k+1.
- If A[x] < k+1, then L(x+1) is A[x].

Thus, L(x+1) = min(L(x) + 1, A[x]) is a recursion for L.

Putting that all together:

```
def solve(A):
A = [0] + A + [0]
def staircase(A):
#L[x] = largest staircase ending at x
L = []
for i, u in enumerate(A):
L.append(min(L[-1] + 1, u) if i else 0)
return L
L = staircase(A)
R = staircase(A[::-1])[::-1]
return max( min(L[i], R[i]) for i in xrange(len(A)) ) + 1
```