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.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	final static int MOD = 1000000007;
	static double start;

	public static void main(String[] args) throws Exception {

		start = System.currentTimeMillis();
		long test = 1;
//		 long test = strToLong(in.readLine().trim()); // if number of
		// test cases
		for (int i = 0; i < test; i++) {
			req();

		}

		out.flush();
		// System.out.println(System.currentTimeMillis() - start + " **");

		out.close();

	}

	public static void req() throws Exception {
		int n = strToInt(in.readLine());
		long arr[] = splits(in.readLine(), n);
		long left[] = new long[n];
		long right[] = new long[n];
		long hash[] = new long[n];
		left[0] = 1;
		right[n-1] = 1;
		for(int i =1;i<n;i++)
		{
			left[i] = min(left[i-1]+1,arr[i]);
		}
		long max = 1;
		for(int i = n-2;i>=0;i--)
		{
			right[i] = min(right[i+1]+1,arr[i]);
			hash[i] = min(right[i],left[i]);
			if(max < hash[i])
				max = hash[i];
		}
		
//		System.out.println(Arrays.toString(left));
//		System.out.println(Arrays.toString(right));
		System.out.println(max);
		
	}

	// takes a string with spaces as input and produces an array of long of
	// length n
	// input should be valid
	// should know length of array beforehand
	static long[] splits(String s, int n) {

		long[] out = new long[n];
		int idx = 0;

		StringTokenizer ss = new StringTokenizer(s);
		while (ss.hasMoreTokens()) {

			out[idx] = strToLong(ss.nextToken());

			idx++;
		}

		return out;

	}

	// like split but first integer in input is nuumber of integer that
	// follows
	static long[] splits2(String s) {

		long[] out;
		int idx = 0;

		StringTokenizer ss = new StringTokenizer(s);
		int n = strToInt(ss.nextToken());
		out = new long[n];
		while (ss.hasMoreTokens()) {
			out[idx] = strToLong(ss.nextToken());

			idx++;
		}

		return out;

	}

	// returns gcd of two long parameters
	// i think its algo by euclid
	static long gcd(long a, long b) {

		return b == 0 ? a : gcd(b, a % b);
	}

	// returns maximum among two long
	public static long max(long a, long b) {
		return a > b ? a : b;
	}

	// modulus of product of two long parameter
	public static long modPro(long a, long b) {
		// check value of MOD , may vary for different questions
		// or change the function to take mod as an input parameter
		// tongue emoticon
		return ((a % MOD) * (b % MOD)) % MOD;
	}

	public static long modInv(long a) {
		return new BigInteger(a + "").modPow(new BigInteger((MOD - 2) + ""), new BigInteger(MOD + "")).longValue();
	}

	// returns minimum among two long
	public static long min(long a, long b) {
		return a < b ? a : b;
	}

	// take a string as input and convert it to an integer
	// takes care of negatives
	// no commas or space expected in string
	// copied from codechef
	public static int strToInt(String str) {
		int i = 0;
		int num = 0;
		boolean isNeg = false;
		// Check for negative sign; if it's there, set the isNeg flag
		if (str.charAt(0) == '-') {
			isNeg = true;
			i = 1;
		}
		// Process each character of the string;
		while (i < str.length()) {
			num *= 10;
			num += str.charAt(i++) - '0'; // Minus the ASCII code of
											// '0' to get
			// the value of the charAt(i++).
		}
		if (isNeg)
			num = -num;
		return num;
	}

	// take a string as input and convert it to a long
	// takes care of negatives
	// no commas or space expected in string
	// copied from codechef
	public static long strToLong(String str) {
		int i = 0;
		long num = 0;
		boolean isNeg = false;
		// Check for negative sign; if it's there, set the isNeg flag
		if (str.charAt(0) == '-') {
			isNeg = true;
			i = 1;
		}
		// Process each character of the string;
		while (i < str.length()) {
			num *= 10;
			num += str.charAt(i++) - '0'; // Minus the ASCII code of
											// '0' to get
			// the value of the charAt(i++).
		}
		if (isNeg)
			num = -num;
		return num;
	}

}