Recently, Mike was very busy with studying for exams and contests. Now he is going to chill a bit by doing some sight seeing in the city.

City consists of n intersections numbered from 1 to n. Mike starts walking from his house located at the intersection number 1 and goes along some sequence of intersections. Walking from intersection number i to intersection j requires |i - j| units of energy. The total energy spent by Mike to visit a sequence of intersections p1 = 1, p2, ..., pk is equal to <image> units of energy.

Of course, walking would be boring if there were no shortcuts. A shortcut is a special path that allows Mike walking from one intersection to another requiring only 1 unit of energy. There are exactly n shortcuts in Mike's city, the ith of them allows walking from intersection i to intersection ai (i ≤ ai ≤ ai + 1) (but not in the opposite direction), thus there is exactly one shortcut starting at each intersection. Formally, if Mike chooses a sequence p1 = 1, p2, ..., pk then for each 1 ≤ i < k satisfying pi + 1 = api and api ≠ pi Mike will spend only 1 unit of energy instead of |pi - pi + 1| walking from the intersection pi to intersection pi + 1. For example, if Mike chooses a sequence p1 = 1, p2 = ap1, p3 = ap2, ..., pk = apk - 1, he spends exactly k - 1 units of total energy walking around them.

Before going on his adventure, Mike asks you to find the minimum amount of energy required to reach each of the intersections from his home. Formally, for each 1 ≤ i ≤ n Mike is interested in finding minimum possible total energy of some sequence p1 = 1, p2, ..., pk = i.

Input

The first line contains an integer n (1 ≤ n ≤ 200 000) — the number of Mike's city intersection.

The second line contains n integers a1, a2, ..., an (i ≤ ai ≤ n , <image>, describing shortcuts of Mike's city, allowing to walk from intersection i to intersection ai using only 1 unit of energy. Please note that the shortcuts don't allow walking in opposite directions (from ai to i).

Output

In the only line print n integers m1, m2, ..., mn, where mi denotes the least amount of total energy required to walk from intersection 1 to intersection i.

Examples

Input

3
2 2 3


Output

0 1 2 


Input

5
1 2 3 4 5


Output

0 1 2 3 4 


Input

7
4 4 4 4 7 7 7


Output

0 1 2 1 2 3 3 

Note

In the first sample case desired sequences are:

1: 1; m1 = 0;

2: 1, 2; m2 = 1;

3: 1, 3; m3 = |3 - 1| = 2.

In the second sample case the sequence for any intersection 1 < i is always 1, i and mi = |1 - i|.

In the third sample case — consider the following intersection sequences:

1: 1; m1 = 0;

2: 1, 2; m2 = |2 - 1| = 1;

3: 1, 4, 3; m3 = 1 + |4 - 3| = 2;

4: 1, 4; m4 = 1;

5: 1, 4, 5; m5 = 1 + |4 - 5| = 2;

6: 1, 4, 6; m6 = 1 + |4 - 6| = 3;

7: 1, 4, 5, 7; m7 = 1 + |4 - 5| + 1 = 3.
import java.util.*;
import java.io.*;
import java.awt.Point;
import java.math.BigDecimal;
import java.math.BigInteger;

import static java.lang.Math.*;


public class __AAAAA implements Runnable{
	
	final static Random rnd = new Random();
	
	// SOLUTION!!! 
	// HACK ME PLEASE IF YOU CAN!!!
	// PLEASE!!!
	// PLEASE!!!
	// PLEASE!!!
	
	void solve() {
		int n = readInt();
		
		int[] a = readIntArray(n);
		for (int i = 0; i < n; ++i) {
			a[i]--;
		}
		
		int[] dp = new int[n];
		Arrays.fill(dp, n);
		dp[0] = 0;
		
		Queue<Integer> queue = new ArrayDeque<Integer>();
		queue.add(0);
		
		while (queue.size() > 0) {
			int from = queue.poll();
			
			int[] tos = { from - 1, from + 1, a[from] };
			for (int to : tos) {
				if (0 <= to && to < n && dp[to] > dp[from] + 1) {
					dp[to] = dp[from] + 1;
					queue.add(to);
				}
			}
		}
		
//		List<Integer>[] starts = new List[n];
//		for (int i = 0; i < n; ++i) {
//			starts[i] = new ArrayList<Integer>();
//		}
//		
//		for (int i = 0; i < n; ++i) {
//			starts[a[i]].add(i);
//		}
//		
//		int[] dp = new int[n];
//		dp[0] = 0;
//		
//		for (int i = 1; i < n; ++i) {
//			dp[i] = dp[i - 1] + 1;
//			for (int start : starts[i]) {
//				dp[i] = Math.min(dp[i], dp[start] + 1);
//			}
//		}
//		
//		for (int i = n - 2; i >= 0; --i) {
//			dp[i] = Math.min(dp[i], dp[i + 1] + 1);
//		}
		
		for (int distance : dp) {
			out.print(distance + " ");
		}
		
		out.println();
	}
	
	/////////////////////////////////////////////////////////////////////
	
	final boolean FIRST_INPUT_STRING = false;
	final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
	
	final static int MAX_STACK_SIZE = 128;
	
	/////////////////////////////////////////////////////////////////////
	
	public void run(){
		try{
			timeBegin = System.currentTimeMillis();
			Locale.setDefault(Locale.US);
			
			init();
			
			if (ONLINE_JUDGE) {
				solve();
			} else {
				while (true) {
					try {
						solve();
						out.println();
					} catch (NumberFormatException e) {
						break;
					} catch (NullPointerException e) {
						if (FIRST_INPUT_STRING) break;
						else throw e;
					}
				}
			}
			
			out.close();
			time();
		}catch (Exception e){
			e.printStackTrace(System.err);
			System.exit(-1);
		}
	}
	
	/////////////////////////////////////////////////////////////////////
	
	BufferedReader in;
	OutputWriter out;
	StringTokenizer tok = new StringTokenizer("");
	
	public static void main(String[] args){
		new Thread(null, new __AAAAA(), "", MAX_STACK_SIZE * (1L << 20)).start();
	}
	
	/////////////////////////////////////////////////////////////////////
	
	void init() throws FileNotFoundException{
		Locale.setDefault(Locale.US);
		
		if (ONLINE_JUDGE){
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new OutputWriter(System.out);
		}else{
			in = new BufferedReader(new FileReader("input.txt"));
			out = new OutputWriter("output.txt");
		}
	}
	
	////////////////////////////////////////////////////////////////
	
	long timeBegin, timeEnd;

	void time(){
		timeEnd = System.currentTimeMillis();
		System.err.println("Time = " + (timeEnd - timeBegin));
	}
	
	void debug(Object... objects){
		if (ONLINE_JUDGE){
			for (Object o: objects){
				System.err.println(o.toString());
			}
		}
	}
	
	/////////////////////////////////////////////////////////////////////
	
	String delim = " ";
	
	String readLine() {
		try {
			return in.readLine();
		} catch (IOException e) {
			throw new RuntimeIOException(e);
		}
	}
	
	String readString() {
		try {
			while(!tok.hasMoreTokens()){
				tok = new StringTokenizer(readLine());
			}
			
			return tok.nextToken(delim);
		} catch (NullPointerException e) {
			return null;
		}
	}
	
	/////////////////////////////////////////////////////////////////
	
	final char NOT_A_SYMBOL = '\0';
	
	char readChar() {
		try {
			int intValue = in.read();
			
			if (intValue == -1){
				return NOT_A_SYMBOL;
			}
			
			return (char) intValue;
		} catch (IOException e) {
			throw new RuntimeIOException(e);
		}
	}
	
	char[] readCharArray() {
		return readLine().toCharArray();
	}
	
	char[][] readCharField(int rowsCount) {
		char[][] field = new char[rowsCount][];
		for (int row = 0; row < rowsCount; ++row) {
			field[row] = readCharArray();
		}
		
		return field;
	}
	
	/////////////////////////////////////////////////////////////////
	
	int readInt() {
		return Integer.parseInt(readString());
	}
	
	int[] readIntArray(int size) {
		int[] array = new int[size];
		
		for (int index = 0; index < size; ++index){
			array[index] = readInt();
		}
		
		return array;
	}
	
	int[] readSortedIntArray(int size) {
		Integer[] array = new Integer[size];
		
		for (int index = 0; index < size; ++index) {
			array[index] = readInt();
		}
		Arrays.sort(array);
		
		int[] sortedArray = new int[size];
		for (int index = 0; index < size; ++index) {
			sortedArray[index] = array[index];
		}
		
		return sortedArray;
	}
	
	int[] readIntArrayWithDecrease(int size) {
		int[] array = readIntArray(size);
		
		for (int i = 0; i < size; ++i) {
			array[i]--;
		}
		
		return array;
	}
	
	///////////////////////////////////////////////////////////////////
	
	int[][] readIntMatrix(int rowsCount, int columnsCount) {
		int[][] matrix = new int[rowsCount][];
		
		for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) {
			matrix[rowIndex] = readIntArray(columnsCount);
		}
		
		return matrix;
	}
	
	int[][] readIntMatrixWithDecrease(int rowsCount, int columnsCount) {
		int[][] matrix = new int[rowsCount][];
		
		for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) {
			matrix[rowIndex] = readIntArrayWithDecrease(columnsCount);
		}
		
		return matrix;
	}
	
	///////////////////////////////////////////////////////////////////
	
	long readLong() {
		return Long.parseLong(readString());
	}
	
	long[] readLongArray(int size) {
		long[] array = new long[size];
		
		for (int index = 0; index < size; ++index){
			array[index] = readLong();
		}
		
		return array;
	}
	
	////////////////////////////////////////////////////////////////////
	
	double readDouble() {
		return Double.parseDouble(readString());
	}
	
	double[] readDoubleArray(int size) {
		double[] array = new double[size];
		
		for (int index = 0; index < size; ++index){
			array[index] = readDouble();
		}
		
		return array;
	}
	
	////////////////////////////////////////////////////////////////////
		
	BigInteger readBigInteger() {
		return new BigInteger(readString());
	}
	
	BigDecimal readBigDecimal() {
		return new BigDecimal(readString());
	}
	
	/////////////////////////////////////////////////////////////////////
	
	Point readPoint() {
		int x = readInt();
		int y = readInt();
		return new Point(x, y);
	}
	
	Point[] readPointArray(int size) {
		Point[] array = new Point[size];
		
		for (int index = 0; index < size; ++index){
			array[index] = readPoint();
		}
		
		return array;
	}
	
	/////////////////////////////////////////////////////////////////////
	
	List<Integer>[] readGraph(int vertexNumber, int edgeNumber) {
		@SuppressWarnings("unchecked")
		List<Integer>[] graph = new List[vertexNumber];
		
		for (int index = 0; index < vertexNumber; ++index){
			graph[index] = new ArrayList<Integer>();
		}
		
		while (edgeNumber-- > 0){
			int from = readInt() - 1;
			int to = readInt() - 1;
			
			graph[from].add(to);
			graph[to].add(from);
		}
		
		return graph;
	}
	
	/////////////////////////////////////////////////////////////////////
	
	static class IntIndexPair {
		
		static Comparator<IntIndexPair> increaseComparator = new Comparator<IntIndexPair>() {
			
			@Override
			public int compare(IntIndexPair indexPair1, IntIndexPair indexPair2) {
				int value1 = indexPair1.value;
				int value2 = indexPair2.value;
				
				if (value1 != value2) return value1 - value2;
				
				int index1 = indexPair1.index;
				int index2 = indexPair2.index;
				
				return index1 - index2;
			}
		};
		
		static Comparator<IntIndexPair> decreaseComparator = new Comparator<IntIndexPair>() {
			
			@Override
			public int compare(IntIndexPair indexPair1, IntIndexPair indexPair2) {
				int value1 = indexPair1.value;
				int value2 = indexPair2.value;
				
				if (value1 != value2) return -(value1 - value2);
				
				int index1 = indexPair1.index;
				int index2 = indexPair2.index;
				
				return index1 - index2;
			}
		};
		
		int value, index;

		public IntIndexPair(int value, int index) {
			super();
			this.value = value;
			this.index = index;
		}		
		
		public int getRealIndex() {
			return index + 1;
		}
	}
	
	IntIndexPair[] readIntIndexArray(int size) {
		IntIndexPair[] array = new IntIndexPair[size];
		
		for (int index = 0; index < size; ++index) {
			array[index] = new IntIndexPair(readInt(), index);
		}
		
		return array;
	}
	
	/////////////////////////////////////////////////////////////////////
	
	static class OutputWriter extends PrintWriter {

		final int DEFAULT_PRECISION = 12;
		
		protected int precision;
		protected String format, formatWithSpace;
		
		{
			precision = DEFAULT_PRECISION;
			
			format = createFormat(precision);
			formatWithSpace = format + " ";
		}
		
		public OutputWriter(OutputStream out) {
			super(out);
		}

		public OutputWriter(String fileName) throws FileNotFoundException {
			super(fileName);
		}
		
		public int getPrecision() {
			return precision;
		}

		public void setPrecision(int precision) {
			precision = max(0, precision);
			this.precision = precision;
			
			format = createFormat(precision);
			formatWithSpace = format + " ";
		}
		
		private String createFormat(int precision){
			return "%." + precision + "f";
		}
		
		@Override
		public void print(double d){
			printf(format, d);
		}
		
		public void printWithSpace(double d){
			printf(formatWithSpace, d);
		}

		public void printAll(double...d){
			for (int i = 0; i < d.length - 1; ++i){
				printWithSpace(d[i]);
			}
			
			print(d[d.length - 1]);
		}
		
		@Override
		public void println(double d){
			printlnAll(d);
		}
		
		public void printlnAll(double... d){
			printAll(d);
			println();
		}
	}
	
	/////////////////////////////////////////////////////////////////////
	
	static class RuntimeIOException extends RuntimeException {

		/**
		 * 
		 */
		private static final long serialVersionUID = -6463830523020118289L;

		public RuntimeIOException(Throwable cause) {
			super(cause);
		}
	}
	
	/////////////////////////////////////////////////////////////////////
	//////////////// Some useful constants and functions ////////////////
	/////////////////////////////////////////////////////////////////////
	
	static final int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 
	static final int[][] steps8 = {
			{-1, 0}, {1, 0}, {0, -1}, {0, 1},
			{-1, -1}, {1, 1}, {1, -1}, {-1, 1}
	};
	
	static final boolean checkCell(int row, int rowsCount, int column, int columnsCount) {
		return checkIndex(row, rowsCount) && checkIndex(column, columnsCount);
	}
	
	static final boolean checkIndex(int index, int lim){
		return (0 <= index && index < lim);
	}
	
	/////////////////////////////////////////////////////////////////////
	
	static final boolean checkBit(int mask, int bit){
		return (mask & (1 << bit)) != 0;
	}
	
	/////////////////////////////////////////////////////////////////////
	
	static final long getSum(int[] array) {
		long sum = 0;
		for (int value: array) {
			sum += value;
		}
		
		return sum;
	}
	
	static final Point getMinMax(int[] array) {
		int min = array[0];
		int max = array[0];
		
		for (int index = 0, size = array.length; index < size; ++index, ++index) {
			int value = array[index];
			
			if (index == size - 1) {
				min = min(min, value);
				max = max(max, value);
			} else {
				int otherValue = array[index + 1];
				
				if (value <= otherValue) {
					min = min(min, value);
					max = max(max, otherValue);
				} else {
					min = min(min, otherValue);
					max = max(max, value);
				}
			}
		}
		
		return new Point(min, max);
	}
	
	/////////////////////////////////////////////////////////////////////
	
	static class IdMap<KeyType> extends HashMap<KeyType, Integer> {

		/**
		 * 
		 */
		private static final long serialVersionUID = -3793737771950984481L;

		public IdMap() {
			super();
		}
		
		int getId(KeyType key) {
			Integer id = super.get(key);
			if (id == null) {
				super.put(key, id = size());
			}
			
			return id;
		}
	}
}

