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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Random;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskD {
		int latestMin;
		int latestMax;

		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			int[] radius = new int[n];
			for (int i = 0; i < n; i++) {
				radius[i] = in.nextInt();
			}

//		boolean stress = true;
			boolean stress = false;
			if (stress) {
				n = 100000;
				Random random = new Random(0);
				radius = new int[n];
				for (int i = 0; i < n; i++) {
					radius[i] = 1;
				}
			}

			int log = 0;
			while ((1 << log) <= n) {
				++log;
			}
			--log;

			int[][] l = new int[log + 1][3 * n];
			int[][] r = new int[log + 1][3 * n];
			int[][] tree = new int[log + 1][2 * 6 * n];
			for (int i = 0; i < n; i++) {
				for (int rep = 0; rep < 3; rep++) {
					l[0][n * rep + i] = Math.max(0, (n * rep + i) - radius[i]);
					r[0][n * rep + i] = Math.min(3 * n - 1, (n * rep + i) + radius[i]);
				}
			}

			for (int step = 0; step <= log; step++) {
				int[] curL = l[step];
				int[] curR = r[step];
				initTree(3 * n, tree[step], curL, curR);
				if (step == log) {
					break;
				}
				int[] nxtL = l[step + 1];
				int[] nxtR = r[step + 1];
				for (int i = 0; i < 3 * n; i++) {
					int a = curL[i];
					int b = curR[i];
					if (b - a + 1 >= n) {
						nxtL[i] = a;
						nxtR[i] = b;
						continue;
					}
					get(tree[step], 3 * n, a, b);
					nxtL[i] = latestMin;
					nxtR[i] = latestMax;
				}
			}

			int[] ans = new int[n];
			for (int i = 0; i < n; i++) {
				int step = log;
				int a = n + i;
				int b = n + i;
				while (step >= 0) {
					get(tree[step], 3 * n, a, b);
					int na = latestMin;
					int nb = latestMax;
					if (nb - na + 1 < n) {
						ans[i] += 1 << step;
						a = na;
						b = nb;
					}
					--step;
				}
				if (b - a + 1 < n) {
					++ans[i];
				}
			}

			for (int i = 0; i < n; i++) {
				if (i > 0) {
					out.print(" ");
				}
				out.print(ans[i]);
			}
			out.println();
		}

		private void initTree(int n, int[] tree, int[] a, int[] b) {
			for (int i = 0; i < 2 * n; i++) {
				tree[2 * i] = (int) 1e9;
				tree[2 * i + 1] = -(int) 1e9;
			}
			for (int i = 0; i < a.length; i++) {
				tree[2 * (i + n)] = a[i];
				tree[2 * (i + n) + 1] = b[i];
			}
			for (int i = 2 * n - 1; i > 0; i--) {
				tree[2 * (i / 2)] = Math.min(tree[2 * (i / 2)], tree[2 * i]);
				tree[2 * (i / 2) + 1] = Math.max(tree[2 * (i / 2) + 1], tree[2 * i + 1]);
			}
		}

		private void get(int[] tree, int n, int l, int r) {
			l += n;
			r += n;
			int lm = tree[2 * l];
			int rm = tree[2 * r];
			int lM = tree[2 * l + 1];
			int rM = tree[2 * r + 1];
			while (r - l > 1) {
				if (l % 2 == 0) {
					lm = Math.min(lm, tree[2 * (l + 1)]);
					lM = Math.max(lM, tree[2 * (l + 1) + 1]);
				}
				if (r % 2 == 1) {
					rm = Math.min(rm, tree[2 * (r - 1)]);
					rM = Math.max(rM, tree[2 * (r - 1) + 1]);
				}
				l /= 2;
				r /= 2;
			}
			latestMin = Math.min(lm, rm);
			latestMax = Math.max(lM, rM);
		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(in.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}

