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.util.*;

public class Main {
	static long mod = 998244353;
  static int size = 200000;
	static long[] fac = new long[size];
	static long[] finv = new long[size];
	static long[] inv = new long[size];
	static int INF = Integer.MAX_VALUE;

 	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] h = new int[n+2];
		h[0] = 0; h[n+1] = 0;
		for(int i = 1; i <= n; i++){
			h[i] = scanner.nextInt();
		}
		int[] l = new int[n+2];
		l[1] = 1;
		for(int i = 1; i <= n; i++){
			if(h[i] > h[i-1]){
				l[i] = l[i-1]+1;
			}else{
				l[i] = Math.min(l[i-1]+1,h[i]);
			}
		}
		int[] r = new int[n+2];
		r[n] = 1;
		for(int i = n; i >= 1; i--){
			if(h[i] > h[i+1]){
				r[i] = r[i+1]+1;
			}else{
				r[i] = Math.min(r[i+1]+1,h[i]);
			}
		}
		int[] lr = new int[n+2];
		int max = 0;
		for(int i = 1; i <= n; i++){
			lr[i] = Math.min(l[i],r[i]);
			max = Math.max(max,lr[i]);
		}
		System.out.println(max);
	}
	public static boolean isPrime(int n){
		if(n == 1) return false;
		if(n == 2 || n == 3) return true;
		for(int i = 2; i <= Math.sqrt(n); i++){
			if(n % i == 0) return false;
		}
		return true;
	}
	// tar の方が数字が大きいかどうか
	static boolean compare(String tar, String src) {
		if (src == null) return true;
		if (src.length() == tar.length()) {
			int len = tar.length();
			for (int i = 0; i < len; i++) {
				if (src.charAt(i) > tar.charAt(i)) {
					return false;
				} else if (src.charAt(i) < tar.charAt(i)) {
					return true;
				}
			}
			return tar.compareTo(src) > 0 ? true : false;
		} else if (src.length() < tar.length()) {
			return true;
		} else if (src.length() > tar.length()) {
			return false;
		}
		return false;
	}
	public static class Edge{
		int from;
		int to;
		Edge(int from, int to){
			this.from = from;
			this.to = to;
		}
	}
	public static void swap(long a, long b){
		long tmp = 0;
		if(a > b){
			tmp = a;
			a = b;
			b = tmp;
		}
	}
  static class Pair implements Comparable<Pair>{
    int first, second;
    Pair(int a, int b){
        first = a;
        second = b;
    }
    @Override
    public boolean equals(Object o){
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair p = (Pair) o;
        return first == p.first && second == p.second;
    }
    @Override
    public int compareTo(Pair p){
        return first == p.first ? second - p.second : first - p.first; //firstで昇順にソート
        //return (first == p.first ? second - p.second : first - p.first) * -1; //firstで降順にソート
        //return second == p.second ? first - p.first : second - p.second;//secondで昇順にソート
        //return (second == p.second ? first - p.first : second - p.second)*-1;//secondで降順にソート
    }
  }

  //繰り返し二乗法
  public static long pow(long x, long n){
    long ans = 1;
    while(n > 0){
      if((n & 1) == 1){
        ans = ans * x;
        ans %= mod;
      }
      x = x * x % mod;
      n >>= 1;
    }
    return ans;
  }

	public static long div(long x, long y){
		return (x*pow(y, mod-2))%mod;
	}

  //fac, inv, finvテーブルの初期化、これ使う場合はinitComb()で初期化必要
	public static  void initComb(){
		fac[0] = finv[0] = inv[0] = fac[1] = finv[1] = inv[1] = 1;
		for (int i = 2; i < size; ++i) {
			fac[i] = fac[i - 1] * i % mod;
			inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod;
			finv[i] = finv[i - 1] * inv[i] % mod;
		}
	}

	//nCk % mod
	public static long comb(int n, int k){
		return fac[n] * finv[k] % mod * finv[n - k] % mod;
	}

	//n! % mod
	public static long fact(int n){
		return fac[n];
	}

	//(n!)^-1 with % mod
	public static long finv(int n){
		return finv[n];
	}

  static class UnionFind {
    int[] parent;
    public UnionFind(int size) {
      parent = new int[size];
      Arrays.fill(parent, -1);
    }
    public boolean unite(int x, int y) {
      x = root(x);
      y = root(y);
      if (x != y) {
        if (parent[y] < parent[x]) {
          int tmp = y;
          y = x;
          x = tmp;
        }
        parent[x] += parent[y];
        parent[y] = x;
        return true;
      }
      return false;
    }
    public boolean same(int x, int y) {
      return root(x) == root(y);
    }
    public int root(int x) {
      return parent[x] < 0 ? x : (parent[x] = root(parent[x]));
    }
    public int size(int x) {
      return -parent[root(x)];
    }
  }
	public static int upperBound(int[] array, int value) {
			 int low = 0;
			 int high = array.length;
			 int mid;
			 while( low < high ) {
					 mid = ((high - low) >>> 1) + low; // (high + low) / 2
					 if( array[mid] <= value ) {
							 low = mid + 1;
					 } else {
							 high = mid;
					 }
			 }
			 return low;
	 }
	 public static final int lowerBound(final int[] arr, final int value) {
    	int low = 0;
    	int high = arr.length;
    	int mid;
    	while (low < high){
        	mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        	if (arr[mid] < value) {
          	low = mid + 1;
        	} else {
            high = mid;
        	}
    	}
    	return low;
		}
  //n,mの最大公約数
  public static long gcd(long n, long m){
    if(m > n) return gcd(m,n);
    if(m == 0) return n;
    return gcd(m, n%m);
  }
	//3要素のソート
	private class Pair2 implements Comparable<Pair2> {
		String s;
		int p;
		int index;
		public Pair2(String s, int p, int index) {
				this.s = s;
				this.p = p;
				this.index = index;
		}

		public int compareTo(Pair2 other) {
				if (s.equals(other.s)) {
						return other.p - this.p;
				}
				return this.s.compareTo(other.s);
		}
	}
	//c -> intに変換
public static int c2i(char c){
	if('A' <= c && c <= 'Z'){
		return c - 'A';
	}else{
		return c - 'a' + 26;
	}
}
// int -> charに変換
public static char i2c(int i){
	if(0 <= i && i < 26){
			return (char)(i + 'A');
	}else{
			return (char)(i + 'a' - 26);
	}
}

}
