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 hi 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 ≤ 105).

The second line contains n space-separated integers h1, h2, ..., hn (1 ≤ hi ≤ 109) — 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.
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class q5 {

	 public static int gcd(int a,int b) {
		 if(b==0) return a;
		 else return gcd(b,a%b);
	 }
	 
	 // Credits to GFG
	 static public int dfs(ArrayList<Integer>[] graph,ArrayList<Integer> arr, int start, int[] visited) {
		 visited[start]=1;
		 boolean leaf=true;
		 int ans=0;
		 int totalchild=0;
		 for(int i:graph[start]) {
			 if(visited[i]==0) {
				 ans+=q5.dfs(graph, arr, i, visited);
				 leaf=false;
			 }
		 }
		 if(leaf) ans=1;
		 arr.add(ans);
		 return ans;
		 
	 }
	 
	 
	  
	  
	
	
	 
	
	 
	 
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		// Editorial implementation for practice
		Reader.init(System.in);
		StringBuffer output=new StringBuffer("");
		PrintWriter out=new PrintWriter(System.out);
		int n=Reader.nextInt();
		int[] arr=new int[n+2];
		for(int i=1;i<=n;i++) arr[i]=Reader.nextInt();
		for(int i=1;i<=n;i++) {
			arr[i]=Math.min(arr[i], arr[i-1]+1);
		}
		for(int i=n;i>=1;i--) {
			arr[i]=Math.min(arr[i], arr[i+1]+1);
		}
		int max=0;
		for(int i=1;i<=n;i++) {
			max=Math.max(max, arr[i]);
		}
		output.append(max);
		out.write(output.toString());
		out.flush();
	}
}

 
class Node2{
	String name;
	double ft,st;
	Node2(String a,double b,double c){
		name=a;
		ft=b;
		st=c;
	}
	
}

class Heap{
	int[] mylist;
	int[] mymap;
	int[] vtxmymap;
	int size;
	long[] update;
	long updatevalue;
	int[] removed;
	Heap(int[] graph){
		int l=graph.length;
		updatevalue=0;
		removed=new int[l];
		update=new long[l];
		size=l-1;
		mylist=new int[l];
		mymap=new int[l];
		vtxmymap=new int[l];
		for(int i=size;i>0;i--) {
			if(i>size/2) {
				mylist[i]=graph[i];
				mymap[i]=i;
				vtxmymap[i]=i;
			}
			else {
				mylist[i]=graph[i];
				mymap[i]=i;
				vtxmymap[i]=i;
				boolean end=false;
				int parent=i;
				while(!end) {
					int leftchild=2*parent;
					int rightchild=2*parent+1;
					if(leftchild>size) {
						end=true;
					}
					else if(rightchild>size) {
						if(mylist[leftchild]<mylist[parent]) {
							int parentNode=vtxmymap[parent];
							int childNode=vtxmymap[leftchild];
							int parentDeg=mylist[parent];
							int childDeg=mylist[leftchild];
							mylist[parent]=childDeg;
							mylist[leftchild]=parentDeg;
							mymap[parentNode]=leftchild;
							mymap[childNode]=parent;
							vtxmymap[parent]=childNode;
							vtxmymap[leftchild]=parentNode;
							parent=leftchild;
						}
						else end=true;
					}
					else {
						if(mylist[leftchild]<=mylist[rightchild]) {
							if(mylist[leftchild]<mylist[parent]) {
								int parentNode=vtxmymap[parent];
								int childNode=vtxmymap[leftchild];
								int parentDeg=mylist[parent];
								int childDeg=mylist[leftchild];
								mylist[parent]=childDeg;
								mylist[leftchild]=parentDeg;
								mymap[parentNode]=leftchild;
								mymap[childNode]=parent;
								vtxmymap[parent]=childNode;
								vtxmymap[leftchild]=parentNode;
								parent=leftchild;
							}
							else end=true;
						}
						else {
							if(mylist[rightchild]<mylist[parent]) {
								int parentNode=vtxmymap[parent];
								int childNode=vtxmymap[rightchild];
								int parentDeg=mylist[parent];
								int childDeg=mylist[rightchild];
								mylist[parent]=childDeg;
								mylist[rightchild]=parentDeg;
								mymap[parentNode]=rightchild;
								mymap[childNode]=parent;
								vtxmymap[parent]=childNode;
								vtxmymap[rightchild]=parentNode;
								parent=rightchild;
							}
							else end=true;
						}
					}
				}
			}
		}
	}
	
	void update(int child) {
		if(update[child]==updatevalue) return;
		boolean end=false;
		while(!end) {
			update[child]=updatevalue;
			int parent=child/2;
			if(parent<1) end=true;
			else {
				if(mylist[parent]>mylist[child]) {
					int parentNode=vtxmymap[parent];
					int childNode=vtxmymap[child];
					int parentDeg=mylist[parent];
					int childDeg=mylist[child];
					mylist[parent]=childDeg;
					mylist[child]=parentDeg;
					mymap[parentNode]=child;
					mymap[childNode]=parent;
					vtxmymap[parent]=childNode;
					vtxmymap[child]=parentNode;
					parent=child;
				}
				else end=true;
			}
		}
	}
	
	int peek() {
		return mylist[1];
	}
	
	int pop() {
		int toreturn=mylist[1];
		removed[vtxmymap[1]]=1;
		mylist[1]=mylist[size];
		int changedNode=vtxmymap[size];
		vtxmymap[1]=changedNode;
		mymap[changedNode]=1;
		boolean end=false;
		size--;
		if(size==0) end=true;
		int parent=1;
		while(!end) {
			int leftchild=2*parent;
			int rightchild=2*parent+1;
			if(leftchild>size) {
				end=true;
			}
			else if(rightchild>size) {
				if(mylist[leftchild]<mylist[parent]) {
					int parentNode=vtxmymap[parent];
					int childNode=vtxmymap[leftchild];
					int parentDeg=mylist[parent];
					int childDeg=mylist[leftchild];
					mylist[parent]=childDeg;
					mylist[leftchild]=parentDeg;
					mymap[parentNode]=leftchild;
					mymap[childNode]=parent;
					vtxmymap[parent]=childNode;
					vtxmymap[leftchild]=parentNode;
					parent=leftchild;
				}
				else end=true;
			}
			else {
				if(mylist[leftchild]<=mylist[rightchild]) {
					if(mylist[leftchild]<mylist[parent]) {
						int parentNode=vtxmymap[parent];
						int childNode=vtxmymap[leftchild];
						int parentDeg=mylist[parent];
						int childDeg=mylist[leftchild];
						mylist[parent]=childDeg;
						mylist[leftchild]=parentDeg;
						mymap[parentNode]=leftchild;
						mymap[childNode]=parent;
						vtxmymap[parent]=childNode;
						vtxmymap[leftchild]=parentNode;
						parent=leftchild;
					}
					else end=true;
				}
				else {
					if(mylist[rightchild]<mylist[parent]) {
						int parentNode=vtxmymap[parent];
						int childNode=vtxmymap[rightchild];
						int parentDeg=mylist[parent];
						int childDeg=mylist[rightchild];
						mylist[parent]=childDeg;
						mylist[rightchild]=parentDeg;
						mymap[parentNode]=rightchild;
						mymap[childNode]=parent;
						vtxmymap[parent]=childNode;
						vtxmymap[rightchild]=parentNode;
						parent=rightchild;
					}
					else end=true;
				}
			}
		}
		
		
		return toreturn;
	}
	
}


 
 class DisJoint {
		int[] parent;
		int[] rank;
		int[] size;
		DisJoint(int n){
			
			parent=new int[n+1];
			rank=new int[n+1];
			for(int i=0;i<=n;i++) {
				parent[i]=i;
			}
		}

		int find(int value) {
			int par=parent[value];
			if(par==value)
				return par;
			parent[value]=find(par);
			return parent[value];
		}
		
		void union(int data1,int data2) {
			int parent1=find(data1);
			int parent2=find(data2);
			if(parent1!=parent2) {
				if(rank[parent1]>=rank[parent2]) {
					parent[parent2]=parent1;
					if(rank[parent1]==rank[parent2])
						rank[parent1]++;
				}
				else {
					parent[parent1]=parent2;	
		}

		}
		}
}

 
 class Reader {
	    static BufferedReader reader;
	    static StringTokenizer tokenizer;
	 
	    /** call this method to initialize reader for InputStream */
	    static void init(InputStream input) {
	        reader = new BufferedReader(
	                     new InputStreamReader(input) );
	        tokenizer = new StringTokenizer("");
	    }
	 
	    /** get next word */
	    static String nextLine() throws IOException{
	    	return reader.readLine();
	    }
	    static String next() throws IOException {
	        while ( ! tokenizer.hasMoreTokens() ) {
	            //TODO add check for eof if necessary
	            tokenizer = new StringTokenizer(
	                   reader.readLine() );
	        }
	        return tokenizer.nextToken();
	    }
	    
	    static int nextInt() throws IOException {
	        return Integer.parseInt( next() );
	    }
	    static long nextLong() throws IOException {
	        return Long.parseLong( next() );
	    }
	    static double nextDouble() throws IOException {
	        return Double.parseDouble( next() );
	    }
	}

