There are n parrots standing in a circle. Each parrot has a certain level of respect among other parrots, namely r_i. When a parrot with respect level x starts chattering, x neighbours to the right and to the left of it start repeating the same words in 1 second. Their neighbours then start repeating as well, and so on, until all the birds begin to chatter.

You are given the respect levels of all parrots. For each parrot answer a question: if this certain parrot starts chattering, how many seconds will pass until all other birds will start repeating it?

Input

In the first line of input there is a single integer n, the number of parrots (1 ≤ n ≤ 10^5).

In the next line of input there are n integers r_1, ..., r_n, the respect levels of parrots in order they stand in the circle (1 ≤ r_i ≤ n).

Output

Print n integers. i-th of them should equal the number of seconds that is needed for all parrots to start chattering if the i-th parrot is the first to start.

Examples

Input


4
1 1 4 1


Output


2 2 1 2 


Input


8
1 2 2 1 5 1 3 1


Output


3 3 2 2 1 2 2 3 
import java.io.*;
import java.util.*;

public class A implements Runnable {
	public static void main (String[] args) {new Thread(null, new A(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");
		
		int n = fs.nextInt();
		int log = Integer.numberOfTrailingZeros(Integer.highestOneBit(n))+1;
		int[] a = fs.nextIntArray(n);

		if(n == 1) {
			System.out.println(0);
			return;
		}
		
		int[] left = new int[3*n], right = new int[3*n];
		for(int i = 0; i < 3*n; i++) {
			int p1 = i-a[i%n], p2 = i+a[i%n];
			if(p1 < 0) p1 = -1; if(p2 >= 3*n) p2 = 3*n;
			left[i] = p1;
			right[i] = p2;
		}

		int[][] liftLeft = new int[log][3*n];
		int[][] liftRight = new int[log][3*n];
		for(int i = 0; i < 3*n; i++) {
			liftLeft[0][i] = left[i];
			liftRight[0][i] = right[i];
		}
		
		for(int lg = 1; lg < log; lg++) {
			RMQ q1 = new RMQ(liftLeft[lg-1], true);
			RMQ q2 = new RMQ(liftRight[lg-1], false);
			
			for(int i = 0; i < 3*n; i++) {
				int prevL = liftLeft[lg-1][i];
				int prevR = liftRight[lg-1][i];
				if(prevL < 0) liftLeft[lg][i] = prevL;
				else liftLeft[lg][i] = q1.query(prevL, Math.min(3*n-1, prevR));
				if(prevR >= 3*n) liftRight[lg][i] = prevR;
				else liftRight[lg][i] = q2.query(Math.max(0, prevL), prevR);
			}
		}
		
		int[] res = new int[n];
		int[] best = new int[3*n], cL = new int[3*n], cR = new int[3*n];
		for(int i = n; i < 2*n; i++) { cL[i] = i; cR[i] = i; }
		for(int lg = log-1; lg >= 0; lg--) {
			RMQ q1 = new RMQ(liftLeft[lg], true);
			RMQ q2 = new RMQ(liftRight[lg], false);
			for(int i = n; i < 2*n; i++) {
				int nL = q1.query(cL[i], cR[i]);
				int nR = q2.query(cL[i], cR[i]);
				if(nR-nL+1 < n && nL >= 0 && nR < 3*n) {
					best[i] += 1<<lg;
					cL[i] = nL; cR[i] = nR;
				}
			}
		}
		for(int i = n; i < 2*n; i++) res[i-n] = ++best[i];
		
		for(int i = 0; i < n; i++) out.print(res[i] + " ");
		out.println();
		out.close();
	}
	
	class RMQ {
		int[][] lift;
		boolean min;

		public RMQ(int[] vs, boolean m) {
			min = m;
			int n = vs.length;
			int maxlog = Integer.numberOfTrailingZeros(Integer.highestOneBit(n)) + 2;
			lift = new int[maxlog][n];
			for (int i = 0; i < n; i++)
				lift[0][i] = vs[i];
			int lastRange = 1;
			for (int lg = 1; lg < maxlog; lg++) {
				for (int i = 0; i < n; i++) {
					if(min) {
						lift[lg][i] = Math.min(lift[lg - 1][i], lift[lg - 1][Math.min(i + lastRange, n - 1)]);
					}
					else {
						lift[lg][i] = Math.max(lift[lg - 1][i], lift[lg - 1][Math.min(i + lastRange, n - 1)]);
					}
				}
				lastRange *= 2;
			}
		}

		public int query(int low, int hi) {
			int range = hi - low + 1;
			int exp = Integer.highestOneBit(range);
			int lg = Integer.numberOfTrailingZeros(exp);
			if(min) return Math.min(lift[lg][low], lift[lg][hi - exp + 1]);
			else return Math.max(lift[lg][low], lift[lg][hi - exp + 1]);
		}
	}
	
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}