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 p_1 = 1, p_2, ..., p_{k} is equal to $\sum_{i = 1}^{k - 1}|p_{i} - p_{i + 1}$ 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 i^{th} of them allows walking from intersection i to intersection a_{i} (i ≤ a_{i} ≤ a_{i} + 1) (but not in the opposite direction), thus there is exactly one shortcut starting at each intersection. Formally, if Mike chooses a sequence p_1 = 1, p_2, ..., p_{k} then for each 1 ≤ i < k satisfying p_{i} + 1 = a_{p}_{i} and a_{p}_{i} ≠ p_{i} Mike will spend only 1 unit of energy instead of |p_{i} - p_{i} + 1| walking from the intersection p_{i} to intersection p_{i} + 1. For example, if Mike chooses a sequence p_1 = 1, p_2 = a_{p}_1, p_3 = a_{p}_2, ..., p_{k} = a_{p}_{k} - 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 p_1 = 1, p_2, ..., p_{k} = 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 a_1, a_2, ..., a_{n} (i ≤ a_{i} ≤ n , $a_{i} \leq a_{i + 1} \forall i < n)$, describing shortcuts of Mike's city, allowing to walk from intersection i to intersection a_{i} using only 1 unit of energy. Please note that the shortcuts don't allow walking in opposite directions (from a_{i} to i).


-----Output-----

In the only line print n integers m_1, m_2, ..., m_{n}, where m_{i} 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; m_1 = 0;

2: 1, 2; m_2 = 1;

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

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

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

1: 1; m_1 = 0;

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

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

4: 1, 4; m_4 = 1;

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

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

7: 1, 4, 5, 7; m_7 = 1 + |4 - 5| + 1 = 3.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list([int(x) - 1 for x in input().split()])

cnt = 0
curr = [0]
v = [0 for _ in range(n)]
r = [0 for _ in range(n)]

lvl = 0
while cnt < n:
    nxt = []
    for i in curr:
        if v[i]:
            continue
        v[i] = 1
        r[i] = lvl
        cnt += 1
        if i > 0 and not v[i-1]:
            nxt.append(i - 1)
        if i < n - 1 and not v[i+1]:
            nxt.append(i + 1)
        if not v[a[i]]:
            nxt.append(a[i])
    curr = nxt
    lvl += 1
print(' '.join(map(str,r)))


n = int(input())
a = [ int(i)-1 for i in input().split() ]

m = [-1]*len(a)

#print(m)

scur = set()
snext = set()

scur.add(0)

dist = 0
changed = True
while changed:
	changed = False
	for i in scur:
		if m[i] == -1 or m[i] > dist:
			m[i] = dist
			if i+1 < n:
				snext.add(i+1)
			if i-1 >= 0:
				snext.add(i-1)
			snext.add(a[i])
			changed = True
	scur = snext
	snext = set()
	dist+=1

for i in m:
	print(i,end=' ')
print()

import sys


def main():
    n = int(sys.stdin.readline())
    x = list(map(int, sys.stdin.readline().split()))
    y = [0]*n
    for i in range(n):
        y[i] = x[i]-1

    q = []
    q.append(0)
    i=0
    res = [-1]*n
    res[0]=0
    while i<len(q):
        c = q[i]
        i+=1
        if c>0 and res[c-1]==-1:
            res[c-1] = res[c]+1
            q.append(c-1)
        if c<n-1 and res[c+1]==-1:
            res[c+1] = res[c]+1
            q.append(c+1)
        if res[y[c]]==-1:
            res[y[c]] = res[c]+1
            q.append(y[c])

    
    print(' '.join(map(str,res)))
    

main()


n=int(input())
shortcuts=input().split()
for i in range (n):
    shortcuts[i]=int(shortcuts[i])-1

mincosts=[]
for i in range (n):
    mincosts.append(i)

for i in range (n-1):
    a=shortcuts[i]
    mincosts[a]=min(mincosts[a],mincosts[i]+1)
    if (i+1<n and shortcuts[i]<shortcuts[i+1]):
        b=a+1
        while (b<=shortcuts[i+1] and mincosts[b-1]+1<mincosts[b]):
            mincosts[b]=mincosts[b-1]+1
            b+=1
        b=a-1
        while (b>i and mincosts[b+1]+1<mincosts[b]):
            mincosts[b]=mincosts[b+1]+1
            b-=1

for i in range (1,n):
    mincosts[i]=min(mincosts[i],mincosts[i-1]+1)

for i in range (n-2,-1,-1):
    mincosts[i]=min(mincosts[i],mincosts[i+1]+1)

for i in range (n):
    mincosts[i]=str(mincosts[i])
print(" ".join(mincosts))


import queue

n = int(input())
values = [ (int(value) - 1) for value in input().split() ]

start = 0

points = queue.Queue()
points.put(start)
d = [n*10] * n
d[start] = 0

while not points.empty():
	value = points.get()
	for destanation in [value - 1, value + 1, values[value]]:
		distance = d[value] + 1
		if destanation < 0 or destanation >= n:
			continue
		elif d[destanation] > distance:
			d[destanation] = distance
			points.put(destanation)

for value in d:
	print(value, end = ' ')

print('')


n = int(input())
s = [0] + list(map(int, input().split()))
ans = [0,0] + [None]*(n-1)

def bfs():
    path = [(s[1],1),(2,1)]
    while path:
        nom, pre = path.pop(0)
        if ans[nom] != None:
            continue
        ans[nom] = pre
        path.append((s[nom], pre+1))
        if nom<n:
            path.append((nom+1, pre+1))
        if nom>2:
            path.append((nom-1, pre+1))

bfs()

for j in range(1,n+1):
    print(ans[j], end=' ')


from heapq import *
n=int(input())
ans=[0]+[n for i in range(n)]
e=[[i+1,i-1] if i<n else [i-1] for i in range(0,n+1)]
e[0],ans[1]=[],0
for i,x in enumerate(map(int,input().split())):
    if i+1!=x: e[i+1]+=[x]
ch=[(0,1)]
while ch:
    l,nom=heappop(ch)
    for x in e[nom]:
        if l+1<ans[x]: ans[x]=l+1; heappush(ch,(l+1,x))
print(*ans[1:])    

n=int(input())
ans=[0]+[n for i in range(n)]
e=[[i+1,i-1] if i<n else [i-1] for i in range(0,n+1)]
e[0],ans[1]=[],0
for i,x in enumerate(map(int,input().split())):
    if i+1!=x: e[i+1]+=[x]
ch=[(0,1)]
while ch:
    l,nom=ch.pop()
    for x in e[nom]:
        if l+1<ans[x]: ans[x]=l+1; ch.append((l+1,x))
print(*ans[1:])    

n=int(input())
ans=[0]+[n for i in range(n)]
e=[[i+1,i-1] if i<n else [i-1] for i in range(0,n+1)]
e[0],ans[1]=[],0
for i,x in enumerate(map(int,input().split())):
    if i+1!=x: e[i+1]+=[x]
ch=[(0,1)]
while ch:
    l,nom=ch.pop(0)
    for x in e[nom]:
        if l+1<ans[x]: ans[x]=l+1; ch.append((l+1,x))
print(*ans[1:])    

#689B
n = int(input())
s = input()
g = {}
src = 0
for i in s.split():
	g[src] = [int(i)-1]
	if src > 0 :
		g[src].append(src-1)
	if src < n-1:
		g[src].append(src+1)
	src+=1
 
energy = [-1]*n
q=[]
q.append(0)
energy[0] = 0
while len(q) > 0 :
	x = q.pop(0)
	for y in g[x]:
		if energy[y] == -1:
			energy[y] = energy[x]+1
			q.append(y)
for i in energy:
	print(i,end = ' ')
	

import sys
from collections import deque

def solve():
    n = int(input())
    a = [val - 1 for val in list(map(int, input().split()))]
    queue = deque([(0, 0)])
    ans = [-1] * n
    while len(queue) > 0:
        cur = queue.popleft()
        if cur[0] < 0 or cur[0] >= n or ans[cur[0]] != -1: continue
        ans[cur[0]] = cur[1]
        queue.append((cur[0] - 1, cur[1] + 1))
        queue.append((cur[0] + 1, cur[1] + 1))
        queue.append((a[cur[0]], cur[1] + 1))
    print(" ".join(map(str, ans)))

if sys.hexversion == 50659824: sys.stdin = open("input.txt")
solve()

import sys
from collections import deque

def solve():
    n = int(input())
    a = [val - 1 for val in list(map(int, input().split()))]
    queue = deque([(0, 0)])
    ans = [-1] * n
    while len(queue) > 0:
        cur = queue.popleft()
        if cur[0] < 0 or cur[0] >= n or ans[cur[0]] != -1: continue
        ans[cur[0]] = cur[1]
        queue.append((cur[0] - 1, cur[1] + 1))
        queue.append((cur[0] + 1, cur[1] + 1))
        queue.append((a[cur[0]], cur[1] + 1))
    print(" ".join(map(str, ans)))

if sys.hexversion == 50659824: sys.stdin = open("input.txt")
solve()

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
    if a[i] <= i + 1:
        a[i] = None

m = [-1] * n
m[0] = 0
now = [0]
next = []
while True:
    if not now:
        break
    for i in now:
        x = m[i] + 1
        if a[i] and m[a[i]] == -1:
            m[a[i]] = x
            next.append(a[i])
        if i != 0 and m[i - 1] == -1:
            m[i - 1] = x
            next.append(i - 1)
        if i != n - 1 and m[i + 1] == -1:
            m[i + 1] = x
            next.append(i + 1)
    now = next
    next = []

print(' '.join(map(str, m)))


#coding gbk
#!usr/bin/env
n = int(input())
a = [0] + [n for i in range(n)]
e = [[i + 1, i - 1] if i < n else [i - 1] for i in range(0, n + 1)]
e[0] = []
a[1] = 0
for i, x in enumerate(map(int, input().split())):
    if i + 1 != x: e[i + 1] += [x]
q = [(0, 1)]
while q:
    l, cur = q.pop(0)
    for x in e[cur]:
        if l + 1 < a[x]:
            a[x] = l + 1
            q.append((l + 1, x))
print(*a[1:])    


def main():
    n = int(input())
    short = [int(fld) - 1 for fld in input().strip().split()]
    assert len(short) == n
    ans = [None] * n
    ans[0] = 0
    justreached = reached = {0}
    step = 0
    while len(reached) < n:
        step += 1
        new = set()
        for i in justreached:
            for j in (i-1, i+1, short[i]):
                if 0 <= j < n and j not in reached:
                    new.add(j)
                    ans[j] = step
        justreached = new
        reached |= new
    print(' '.join(map(str, ans)))
                
    

main()

"""
Codeforces Round #361 (Div. 2)

Problem 689 B. Mike and Shortcuts

@author yamaton
@date 2016-07-09
"""

import itertools as it
import functools
import operator
import collections
import math
import sys


def solve(xs, n):
    nodes = list(range(1, n+1))

    neighbors = collections.defaultdict(set)
    for from_, to_ in zip(nodes, nodes[1:]):
        neighbors[from_].add(to_)
        neighbors[to_].add(from_)
    for from_, to_ in enumerate(xs, 1):
        neighbors[from_].add(to_)

    distance = {1: 0}
    q = collections.deque([1])
    while q:
        node = q.popleft()
        for x in neighbors[node]:
            if x not in distance:
                distance[x] = distance[node] + 1
                q.append(x)
    return [distance[i] for i in nodes]


def pp(*args, **kwargs):
    return print(*args, file=sys.stderr, **kwargs)


def main():
    n = int(input())
    xs = [int(s) for s in input().strip().split()]
    assert len(xs) == n
    result = solve(xs, n)
    print(*result)


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))

g = []

for i in range(n):
    To = set()
    if i < n - 1:
        To.add(i+1)
    if i > 0:
        To.add(i-1)
    if a[i] - 1 != i:
        To.add(a[i]-1)
    g.append(To)

q = [0]
used = [i == 0 for i in range(n)]
d = [0 for i in range(n)]
p = [0 for i in range(n)]
p[0] = -1

while len(q) > 0:
    v = q[0]
    q.pop(0)

    for to in g[v]:
        if not used[to]:
            used[to] = True
            q.append(to)
            d[to] = d[v] + 1
            p[to] = v

for r in d:
    print(r, end=' ')


n = int(input())
dp = [0] + [n] * n + [0]
a = tuple(map(int, input().split()))
s = [1]
dp[1] = 0
while s:
    ns = []
    for v in s:
        if dp[v - 1] == n:
            ns.append(v - 1)
        dp[v - 1] = min(dp[v - 1], dp[v] + 1)
        if dp[v + 1] == n:
            ns.append(v + 1)
        dp[v + 1] = min(dp[v + 1], dp[v] + 1)
        if dp[a[v - 1]] == n:
            ns.append(a[v - 1])
        dp[a[v - 1]] = min(dp[a[v - 1]], dp[v] + 1)
    s = ns
print(' '.join(map(str, dp[1:-1])))


n = int(input())
dp = [0, 0] + [n] * (n - 1) + [0]
a = tuple(map(int, input().split()))
q = [1]
while q:
    v = q.pop(0)
    if dp[v - 1] == n:
        q.append(v - 1)
    dp[v - 1] = min(dp[v - 1], dp[v] + 1)
    if dp[v + 1] == n:
        q.append(v + 1)
    dp[v + 1] = min(dp[v + 1], dp[v] + 1)
    if dp[a[v - 1]] == n:
        q.append(a[v - 1])
    dp[a[v - 1]] = min(dp[a[v - 1]], dp[v] + 1)
print(' '.join(map(str, dp[1:-1])))


n = int(input())
dp = [0, 0] + [n] * (n - 1) + [0]
a = tuple(map(int, input().split()))
i, q = 0, [1]
while i < n:
    v = q[i]
    i += 1
    if dp[v - 1] == n:
        q.append(v - 1)
    dp[v - 1] = min(dp[v - 1], dp[v] + 1)
    if dp[v + 1] == n:
        q.append(v + 1)
    dp[v + 1] = min(dp[v + 1], dp[v] + 1)
    if dp[a[v - 1]] == n:
        q.append(a[v - 1])
    dp[a[v - 1]] = min(dp[a[v - 1]], dp[v] + 1)
print(' '.join(map(str, dp[1:-1])))


n = int(input())
dp = [0, 0] + [n] * (n - 1) + [0]
a = tuple(map(int, input().split()))
i, q = 0, [1]
while i < n:
    v = q[i]
    i += 1
    if dp[v - 1] == n:
        q.append(v - 1)
    dp[v - 1] = min(dp[v - 1], dp[v] + 1)
    if dp[v + 1] == n:
        q.append(v + 1)
    dp[v + 1] = min(dp[v + 1], dp[v] + 1)
    if dp[a[v - 1]] == n:
        q.append(a[v - 1])
    dp[a[v - 1]] = min(dp[a[v - 1]], dp[v] + 1)
print(*dp[1:-1])


def main():
    n = int(input())
    aa = list(map(int, input().split()))
    l, nxt = [n] * (n + 1), [0]
    l[0] = l[n] = 0
    for t in range(1, n):
        cur, nxt = nxt, []
        for v in cur:
            for u in v - 1, v + 1, aa[v] - 1:
                if l[u] > t:
                    l[u] = t
                    nxt.append(u)
        if not nxt:
            break
    del l[n]
    print(' '.join(map(str, l)))


def __starting_point():
    main()

__starting_point()

n=int(input())
l=list(map(int, input().split(' ')))

out=[-1]*n

pas = 0
pos = [0]
out[0]=0

while pos :
    pas+=1
    new_pos=[]
    for p in pos :
        for q in [p-1,p+1,l[p]-1] :
            if q>=0 and q<n and out[q]==-1:
                out[q]=pas
                new_pos.append(q)
    pos = new_pos
    
print(*out)