n=gets.to_i
a=gets.split.map &:to_i
f=2e9
r=0...n
d=r.map{[f]*n}
e=r.map{[f]*n}
d[0][n-1]=e[0][n-1]=0
n.downto(1){|k|(n-k).times{|i|d[i+1][j=i+k]=[d[i+1][j],[[d[i][j],e[i][j]+k].min,a[i]].max+1].min
e[i][j-1]=[d[i][j-1],[[d[i][j]+k,e[i][j]].min,a[j]].max+1].min}}
p r.map{|i|[[d[i][i],e[i][i]].min,a[i]].max}.min