Limak is a little bear who loves to play. Today he is playing by destroying block towers. He built n towers in a row. The i-th tower is made of h_{i} identical blocks. For clarification see picture for the first sample.

Limak will repeat the following operation till everything is destroyed.

Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor. Otherwise, block is boundary. In one operation Limak destroys all boundary blocks. His paws are very fast and he destroys all those blocks at the same time.

Limak is ready to start. You task is to count how many operations will it take him to destroy all towers.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 10^5).

The second line contains n space-separated integers h_1, h_2, ..., h_{n} (1 ≤ h_{i} ≤ 10^9) — sizes of towers.


-----Output-----

Print the number of operations needed to destroy all towers.


-----Examples-----
Input
6
2 1 4 6 2 2

Output
3

Input
7
3 3 3 1 3 3 3

Output
2



-----Note-----

The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color.  [Image]  After first operation there are four blocks left and only one remains after second operation. This last block is destroyed in third operation.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Data structures

Mathematics
Skill types: Dynamic programming

Sorting

Data structures

Starter code:

Solutions:
x = int(input())
mas = list(map(int, input().split(' ')))
mas2 = [0] * x
mas2[0] = 1
for i in range(1, x):
	mas2[i] = min(mas[i], mas2[i - 1] + 1)
mas2[-1] = 1
for i in range(2, x + 1):
	mas2[-i] = min(mas[-i], mas2[-i + 1] + 1, mas2[-i])
print(max(mas2))


n = int(input())
a = [int(x) for x in input().split()]
res = [0] * n
for i in range(n):
	res[i] = [0, 0, 0]
if n < 3:
	print(1)
else:
	res[0][0] = 1
	res[-1][0] = 1
	for i in range(1, n - 1):
		res[i][0] = min(a[i - 1] + 1, a[i + 1] + 1, a[i])
	cur_min = 0
	for i in range(0, n):
		res[i][1] = cur_min + 1
		cur_min = min(res[i][0], res[i][1])
	cur_min = 0
	for i in range(n - 1, -1, -1):
		res[i][2] = cur_min + 1
		cur_min = min(res[i][0], res[i][2])
	tres = min(res[0])
	for k in res:
		tres = max(tres, min(k))
	print(tres)


n = int(input())
a = [int(x) for x in input().split()]
a[0] = 1
a[-1] = 1
for i in range(1, n):
	a[i] = min(a[i], a[i - 1] + 1)
	a[-i] = min(a[-i], a[-(i - 1)] + 1)
print(max(a))


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def check(H, N, K):
	for i in range(K + 1, N - K + 1):
		h = H[i]
		for j in range(K + 1):
			if h <= 0:
				break
			if i - j >= 0:
				h = min(h, H[i - j] - (K - j))
			if i + j <= N:
				h = min(h, H[i + j] - (K - j))
		if h > 0:
			return False
	return True

def solve2(N, A):
	A = [0] + A + [0]
	(lo, hi) = (0, N // 2 + 1)
	while lo <= hi:
		k = (lo + hi) // 2
		if check(A, N, k):
			hi = k - 1
		else:
			lo = k + 1
	return lo

def solve(N, A):
	A = [0] + A + [0]
	H = [N] * (N + 2)
	H[0] = H[-1] = 0
	worst = 0
	for i in range(1, N + 1):
		worst = min(worst, A[i] - i)
		H[i] = i + worst
	worst = N + 1
	for i in range(N, 0, -1):
		worst = min(worst, A[i] + i)
		H[i] = min(H[i], worst - i)
	return max(H)
N = int(input())
A = [int(x) for x in input().split()]
print(solve(N, A))


import sys
try:
	while True:
		n = int(input())
		height = list(map(int, input().split(' ')))
		L = [0 for i in range(100001)]
		R = [0 for i in range(100001)]
		for i in range(n):
			L[i + 1] = min(L[i] + 1, height[i])
		for i in range(n - 1, -1, -1):
			R[i] = min(R[i + 1] + 1, height[i])
		ans = 0
		for i in range(1, n + 1):
			ans = max(ans, min(R[i - 1], L[i]))
		print(ans)
except EOFError:
	pass


n = int(input())
h = [0] + list(map(int, input().split()))
res = [0] * (n + 1)
Min = 0
for i in range(1, n + 1):
	Min = min(Min, h[i] - i)
	res[i] = i + Min
Min = n + 1
for i in range(n, 0, -1):
	Min = min(Min, h[i] + i)
	res[i] = min(res[i], Min - i)
ans = max(res)
print(ans)


def main():
	n = int(input())
	hts = list(map(int, input().split()))
	dpleft = [1]
	for i in range(1, n):
		dpleft.append(min(hts[i], dpleft[-1] + 1))
	hts.reverse()
	dpright = [1]
	for i in range(1, n):
		dpright.append(min(hts[i], dpright[-1] + 1))
	dpright.reverse()
	ans = 0
	for i in range(n):
		ans = max(ans, min(dpleft[i], dpright[i]))
	print(ans)
main()


n = int(input())
x = list(map(int, input().split()))
(pre, suf, ans) = ([0] * n, [0] * n, 0)
for i in range(n):
	if i == 0:
		pre[i] = 1
	else:
		pre[i] = min(pre[i - 1] + 1, x[i])
for i in range(n - 1, -1, -1):
	if i == n - 1:
		suf[i] = 1
	else:
		suf[i] = min(suf[i + 1] + 1, x[i])
	ans = max(ans, min(pre[i], suf[i]))
print(ans)


def powmod(x, p, m):
	if p <= 0:
		return 1
	if p <= 1:
		return x % m
	return powmod(x * x % m, p // 2, m) * (x % m) ** (p % 2) % m
n = int(input())
h = [0] + [int(x) for x in input().split()] + [0]
for i in range(1, len(h)):
	h[i] = min(h[i], h[i - 1] + 1)
	h[-i - 1] = min(h[-i - 1], h[-i] + 1)
ans = max(h)
print(ans)


n = int(input())
h = list(map(int, input().split()))
dp = []
dp.append(1)
for i in range(1, n - 1, 1):
	dp.append(min(dp[i - 1] + 1, h[i]))
dp.append(1)
for i in range(n - 2, 0, -1):
	dp[i] = min(dp[i], dp[i + 1] + 1)
mx = -1
for i in range(n):
	mx = max(mx, dp[i])
print(mx)


from sys import stdin as si
from collections import Counter as c

class Solution:

	def bazinga(self, n, m):
		m[0] = 1
		for i in range(1, n - 1):
			m[i] = min(m[i - 1] + 1, m[i], i + 1)
		m[n - 1] = 1
		for i in range(n - 2, -1, -1):
			m[i] = min(m[i], m[i + 1] + 1)
		return max(m)
n = int(si.readline().strip())
m = list(map(int, si.readline().strip().split()))
S = Solution()
print(S.bazinga(n, m))


import sys
from math import gcd, sqrt, ceil, log2
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
sys.setrecursionlimit(2 * 10 ** 5 + 10)
import heapq
from itertools import permutations
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
aa = 'abcdefghijklmnopqrstuvwxyz'

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = []
	while n % 2 == 0:
		sa.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.append(i)
			n = n // i
	if n > 2:
		sa.append(n)
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def check_prim(n):
	if n < 0:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def getZarr(string, z):
	n = len(string)
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and string[r - l] == string[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and string[r - l] == string[r]:
					r += 1
				z[i] = r - l
				r -= 1

def search(text, pattern):
	concat = pattern + '$' + text
	l = len(concat)
	z = [0] * l
	getZarr(concat, z)
	ha = []
	for i in range(l):
		if z[i] == len(pattern):
			ha.append(i - len(pattern) - 1)
	return ha

def mergeIntervals(arr):
	arr.sort(key=lambda x: x[0])
	m = []
	s = -10000
	max = -100000
	for i in range(len(arr)):
		a = arr[i]
		if a[0] > max:
			if i != 0:
				m.append([s, max])
			max = a[1]
			s = a[0]
		elif a[1] >= max:
			max = a[1]
	if max != -100000 and [s, max] not in m:
		m.append([s, max])
	return m

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def sol(n):
	seti = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			seti.add(n // i)
			seti.add(i)
	return seti

def lcm(a, b):
	return a * b // gcd(a, b)

def moore_voting(l):
	count1 = 0
	count2 = 0
	first = 10 ** 18
	second = 10 ** 18
	n = len(l)
	for i in range(n):
		if l[i] == first:
			count1 += 1
		elif l[i] == second:
			count2 += 1
		elif count1 == 0:
			count1 += 1
			first = l[i]
		elif count2 == 0:
			count2 += 1
			second = l[i]
		else:
			count1 -= 1
			count2 -= 1
	for i in range(n):
		if l[i] == first:
			count1 += 1
		elif l[i] == second:
			count2 += 1
	if count1 > n // 3:
		return first
	if count2 > n // 3:
		return second
	return -1
n = int(input())
l = list(map(int, input().split()))
dp = [10 ** 18] * n
for i in range(n):
	if i == 0:
		dp[i] = 1
	elif l[i] >= l[i - 1]:
		dp[i] = min(l[i], dp[i - 1] + 1, dp[i])
	else:
		dp[i] = min(l[i], dp[i], dp[i - 1] + 1)
l.reverse()
dp.reverse()
for i in range(n):
	if i == 0:
		dp[i] = 1
	elif l[i] >= l[i - 1]:
		dp[i] = min(l[i], dp[i - 1] + 1, dp[i])
	else:
		dp[i] = min(l[i], dp[i], dp[i - 1] + 1)
print(max(dp))


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	h = list(map(int, input().split()))
	ans = h[:]
	(ans[0], ans[-1]) = (1, 1)
	for i in range(1, n):
		ans[i] = min(ans[i], ans[i - 1] + 1)
	for i in range(n - 2, -1, -1):
		ans[i] = min(ans[i], ans[i + 1] + 1)
	print(max(ans))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
ar = list(map(int, input().split()))
r = []
l = []
day = 0
for i in ar:
	day += 1
	day = min(i, day)
	l.append(day)
day = 0
for i in reversed(ar):
	day += 1
	day = min(i, day)
	r.append(day)
ans = 0
x = 0
kk = n - 1
while x < n:
	ans = max(ans, min(r[kk], l[x]))
	x += 1
	kk -= 1
print(ans)


from pprint import pprint
import sys
input = sys.stdin.readline
n = int(input())
dat = list(map(int, input().split()))
datl = [-1] * n
datr = [-1] * n
res = [-1] * n
for i in range(n):
	datl[i] = min(i + 1, dat[i])
	if i > 0:
		datl[i] = min(datl[i], datl[i - 1] + 1)
for i in range(n):
	datr[n - 1 - i] = min(i + 1, dat[n - 1 - i])
	if i > 0:
		datr[n - 1 - i] = min(datr[n - 1 - i], datr[n - 1 - i + 1] + 1)
for i in range(n):
	res[i] = min(datl[i], datr[i])
print(max(res))


input()

def f(l):
	c = [0] * len(l)
	c[0] = c[len(c) - 1] = 9999999
	for item in range(1, len(l) - 1):
		c[item] = min(item, l[item], c[item - 1] + 1)
	for item in reversed(range(1, len(l) - 1)):
		c[item] = min(c[item], len(l) - 2 + 1 - item, c[item + 1] + 1)
	return max(c[1:-1])
print(f([0] + list(map(int, input().split())) + [0]))


x = int(input())
y = list(map(int, input().split(' ')))
y[0] = 1
y[x - 1] = 1
z = y[:]
for i in range(1, x):
	z[i] = min(z[i], z[i - 1] + 1)
w = y[:]
for i in range(x - 2, -1, -1):
	w[i] = min(w[i], w[i + 1] + 1)
ans = 0
for i in range(x):
	ans = max(ans, min(z[i], w[i]))
print(ans)


R = lambda : map(int, input().split())
n = int(input())
arr = [-1] + list(R()) + [-1]
(dpl, dpr) = (arr[:], arr[:])
for i in range(1, n + 1):
	dpl[i] = max(0, min(dpl[i - 1] + 1, arr[i] - 1))
for i in range(n, 0, -1):
	dpr[i] = max(0, min(dpr[i + 1] + 1, arr[i] - 1))
print(1 + max((min(l, r) for (l, r) in zip(dpl, dpr))))


import heapq
n = int(input())
h = list(map(int, input().split()))
g = [[] for i in range(n + 1)]
for i in range(n - 1):
	g[i + 1].append((i, 1))
	g[i].append((i + 1, 1))
for i in range(n):
	g[n].append((i, h[i]))
	g[n].append((i, min(i + 1, n - i)))
hq = []
heapq.heappush(hq, (0, n))
INF = 10 ** 18
d = [INF] * (n + 1)
d[n] = 0
visit = [False] * (n + 1)
while hq:
	(cost, node) = heapq.heappop(hq)
	visit[node] = True
	for (to, val) in g[node]:
		if not visit[to] and d[to] > d[node] + val:
			d[to] = d[node] + val
			heapq.heappush(hq, (d[to], to))
print(max(d))


def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	dpl = [1] * n
	dpr = [1] * n
	for i in range(1, n):
		dpl[i] = min(dpl[i - 1] + 1, a[i])
	for i in range(n - 2, -1, -1):
		dpr[i] = min(dpr[i + 1] + 1, a[i])
	ans = 0
	for i in range(n):
		ans = max(ans, min(dpl[i], dpr[i]))
	print(ans)
main()


n = int(input())
h = list(map(int, input().split()))
min_h = 1
for i in range(n):
	if h[i] > min_h:
		h[i] = min_h
	else:
		min_h = h[i]
	min_h += 1
min_h = 1
for i in range(n - 1, -1, -1):
	if h[i] > min_h:
		h[i] = min_h
	else:
		min_h = h[i]
	min_h += 1
print(max(h))


def main():
	input()
	hh = list(map(int, input().split()))
	for f in (True, False):
		m = 1
		for (i, h) in enumerate(hh):
			if h > m:
				hh[i] = m
			else:
				m = h
			m += 1
		if f:
			hh.reverse()
	print(max(hh))
main()


__author__ = 'JohnHook'
n = list(map(int, input().split()))[0] + 2
a = [0] + list(map(int, input().split())) + [0]
d = [0]
for i in range(1, n):
	if a[i] >= d[i - 1] + 1:
		d.append(d[i - 1] + 1)
		continue
	d.append(a[i])
d.reverse()
a.reverse()
for i in range(1, n):
	if a[i] >= d[i - 1] + 1:
		d[i] = min(d[i], d[i - 1] + 1)
		continue
	d[i] = a[i]
print(max(d))


input()
(l, r) = ([0], [0])
for (a, b) in (lambda a: list(zip(a, reversed(a))))([0] + list(map(int, input().split())) + [0]):
	l.append(min(a, l[-1] + 1))
	r.append(min(b, r[-1] + 1))
print(max(list(map(min, list(zip(l[1:], reversed(r[1:])))))))


n = int(input())
a = [0] + [int(i) for i in input().split()] + [0]
(l, r) = ([0] * (n + 2), [0] * (n + 2))
for i in range(1, n + 1):
	l[i] = min(a[i], l[i - 1] + 1)
for i in range(n, 0, -1):
	r[i] = min(a[i], r[i + 1] + 1)
ans = 0
for i in range(1, n + 1):
	ans = max(ans, min(l[i], r[i]))
print(ans)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
PI = float('inf')
for _ in range(1):
	n = nmbr()
	a = lst()
	ans = 0
	pre = [0] * n
	suf = [0] * n
	pre[0] = suf[n - 1] = 1
	for i in range(1, n):
		pre[i] = min(1 + pre[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		suf[i] = min(1 + suf[i + 1], a[i])
	for (pp, ss) in zip(pre, suf):
		ans = max(ans, min(pp, ss))
	print(ans)


from math import inf
n = int(input())
l = [int(i) for i in input().split()]
l.append(0)
l.insert(0, 0)
minus = [v - i for (i, v) in enumerate(l)]
plus = [v + i for (i, v) in enumerate(l)]
(lminus, rplus) = ([minus[0]], [plus[-1]])
for i in range(1, n + 1):
	lminus.append(min(lminus[-1], minus[i]))
lminus.append(inf)
for i in range(n, 0, -1):
	rplus.append(min(rplus[-1], plus[i]))
rplus.append(inf)
rplus.reverse()
m = 0
for i in range(1, n + 1):
	x = min(lminus[i] + i, rplus[i] - i)
	m = max(m, x)
print(m)


n = int(input())
arr = [0] + [int(i) for i in input().split()] + [0]
(left, right) = ([0] * (n + 2), [0] * (n + 2))
for i in range(1, n + 1):
	left[i] = min(arr[i], left[i - 1] + 1)
for i in range(n, 0, -1):
	right[i] = min(arr[i], right[i + 1] + 1)
ans = 0
for i in range(1, n + 1):
	ans = max(ans, min(left[i], right[i]))
print(ans)