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: MEDIUM_HARD
Tags: Greedy algorithms

Graph algorithms

Graph traversal

Shortest paths
Skill types: Greedy algorithms

Starter code:

Solutions:
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)


n = int(input())
a = list(map(int, input().split()))
res = [0] + [-1] * (n - 1)
idx = [0]
for u in idx:
	for v in [u - 1, u + 1, a[u] - 1]:
		if v >= 0 and v < n and (res[v] == -1):
			res[v] = res[u] + 1
			idx.append(v)
print(*res)


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=' ')


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:])


import queue
n = int(input())
a = input().split(' ')
used = []
d = []
for i in range(0, n):
	used.append(False)
	d.append(-1)
q = queue.Queue()
q.put(0)
d[0] = 0
while not q.empty():
	v = q.get()
	for dl in range(-1, +2):
		u = v + dl
		if 0 <= u and u < n and (d[u] == -1):
			d[u] = d[v] + 1
			q.put(u)
	u = int(a[v]) - 1
	if d[u] == -1:
		d[u] = d[v] + 1
		q.put(u)
for i in range(0, n):
	print(d[i])


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())
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=' ')


import sys
input = sys.stdin.readline
from queue import Queue
t = 1
import math

def bfs(a, i, dis, vis):
	vis[i] = 1
	pp = Queue()
	pp.put(i)
	while not pp.empty():
		z = pp.get()
		vis[z] = 1
		for j in a[z]:
			if vis[j] == 0:
				vis[j] = 1
				dis[j] = min(dis[j], dis[z] + 1)
				pp.put(j)
while t > 0:
	t -= 1
	n = int(input())
	b = [int(x) for x in input().split()]
	a = [[] for i in range(n + 1)]
	for i in range(n):
		x = i + 1
		y = b[i]
		if i != n - 1:
			a[i + 1].append(i + 2)
		if i != 0:
			a[i + 1].append(i)
		if x == y:
			continue
		a[x].append(y)
	vis = [0 for i in range(n + 1)]
	dis = [i - 1 for i in range(n + 1)]
	bfs(a, 1, dis, vis)
	for i in range(1, n + 1):
		print(dis[i], end=' ')


from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
adj = [[] for _ in range(n + 1)]
for (start, end) in zip(range(1, n + 1), gil()):
	if end > start + 1:
		adj[start].append(end)
for start in range(1, n + 1):
	if start + 1 <= n:
		adj[start].append(start + 1)
	if start - 1:
		adj[start].append(start - 1)
d = [inf] * (n + 1)
d[1] = 0
h = [(0, 1)]
while h:
	(dist, node) = heappop(h)
	if dist != d[node]:
		continue
	for c in adj[node]:
		if d[c] > dist + 1:
			d[c] = dist + 1
			heappush(h, (d[c], c))
print(*d[1:])


import sys
input = sys.stdin.readline
import heapq
n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(n)]
for i in range(n):
	if i + 1 < n:
		g[i].append(i + 1)
	if i > 0:
		g[i].append(i - 1)
	g[i].append(a[i] - 1)
d = [10 ** 18] * n
q = [0]
d[0] = 0
while q:
	ver = q.pop()
	for to in g[ver]:
		if d[to] > d[ver] + 1:
			d[to] = d[ver] + 1
			q.append(to)
print(*d)


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 sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dp = [-1] * n
dp[0] = 0
que = [0]
while que:
	k = que.pop(0)
	for v in [k - 1, k + 1, a[k] - 1]:
		if 0 <= v < n and dp[v] == -1:
			dp[v] = dp[k] + 1
			que.append(v)
print(*dp)


import queue
MAX = 1000000000
n = int(input())
a = list(map(int, input().split()))
mov = [-1, 1, 0]
q = queue.Queue()
dist = [MAX] * n
dist[0] = 0
q.put(0)
while q.empty() == False:
	cur = q.get()
	for i in range(len(mov)):
		if i != 2:
			nex = cur + mov[i]
		else:
			nex = a[cur] - 1
		if 0 <= nex and nex < n and (dist[nex] > dist[cur] + 1):
			dist[nex] = dist[cur] + 1
			q.put(nex)
print(' '.join(map(str, dist)))


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])))


intersections_number = int(input())
shortcuts = list(map(int, input().split()))
shortcuts = [shortcut - 1 for shortcut in shortcuts]
distances = [0] + [-1] * (intersections_number - 1)
i = 0
queue = [0]
while i < len(queue):
	ith_intersection = queue[i]
	shortcut = shortcuts[ith_intersection]
	if distances[shortcut] == -1:
		distances[shortcut] = distances[ith_intersection] + 1
		queue.append(shortcut)
	if ith_intersection < intersections_number - 1:
		if distances[ith_intersection + 1] == -1:
			distances[ith_intersection + 1] = distances[ith_intersection] + 1
			queue.append(ith_intersection + 1)
	if ith_intersection > 0:
		if distances[ith_intersection - 1] == -1:
			distances[ith_intersection - 1] = distances[ith_intersection] + 1
			queue.append(ith_intersection - 1)
	i += 1
print(' '.join(map(str, distances)))


from collections import deque
intersections = int(input())
shortcuts = [0] + list(map(int, input().split()))
costs = [float('inf')] * (intersections + 1)
costs[1] = 0
queue = deque([1])
while queue:
	t = queue.popleft()
	if t + 1 <= intersections and costs[t] + 1 < costs[t + 1]:
		costs[t + 1] = costs[t] + 1
		queue.append(t + 1)
	if t - 1 >= 1 and costs[t] + 1 < costs[t - 1]:
		costs[t - 1] = costs[t] + 1
		queue.append(t - 1)
	if costs[t] + 1 < costs[shortcuts[t]]:
		costs[shortcuts[t]] = costs[t] + 1
		queue.append(shortcuts[t])
print(' '.join((str(i) for i in costs[1:])))


from collections import deque
n = int(input())
a = list(map(int, input().split()))
used = [False] * n
d = [-1] * n
q = deque()
q.append(0)
while len(q) > 0:
	v = q.popleft()
	for dx in range(-1, 2):
		u = v + dx
		if 0 <= u and u < n and (d[u] == -1):
			d[u] = d[v] + 1
			q.append(u)
	u = a[v] - 1
	if d[u] == -1:
		d[u] = d[v] + 1
		q.append(u)
for i in range(n):
	print(d[i], 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:])


import queue
n = int(input())
shortcuts = list(map(int, input().split()))
distances = [-1] * n
visited = [False] * n
queue = queue.Queue()
queue.put(0)
distances[0] = 0
while not queue.empty():
	vertex = queue.get()
	for j in range(-1, 2):
		v = vertex + j
		if 0 <= v and v < n and (distances[v] == -1):
			distances[v] = distances[vertex] + 1
			queue.put(v)
	v = shortcuts[vertex] - 1
	if distances[v] == -1:
		distances[v] = distances[vertex] + 1
		queue.put(v)
print(' '.join(map(str, distances)))


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:])


import sys
input = sys.stdin.readline
from queue import Queue
t = 1
import math

def bfs(a, i, dis, vis):
	vis[i] = 1
	s = 0
	e = 0
	pp = [0 for i in range(n + 5)]
	pp[0] = i
	while s != e + 1:
		z = pp[s]
		s += 1
		vis[z] = 1
		for j in a[z]:
			if vis[j] == 0:
				dis[j] = min(dis[j], dis[z] + 1)
				e += 1
				pp[e] = j
				vis[j] = 1
while t > 0:
	t -= 1
	n = int(input())
	b = [int(x) for x in input().split()]
	a = [[] for i in range(n + 1)]
	for i in range(n):
		x = i + 1
		y = b[i]
		if i != n - 1:
			a[i + 1].append(i + 2)
		if i != 0:
			a[i + 1].append(i)
		if x == y:
			continue
		a[x].append(y)
	vis = [0 for i in range(n + 1)]
	dis = [i - 1 for i in range(n + 1)]
	bfs(a, 1, dis, vis)
	for i in range(1, n + 1):
		print(dis[i], end=' ')


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('')


from queue import Queue
n = int(input())
a = input().split()
passados = []
dist = []
for i in range(0, n):
	passados.append(False)
	dist.append(-1)
fila = Queue()
fila.put(0)
dist[0] = 0
while not fila.empty():
	no = fila.get()
	for dis in range(-1, +2):
		resposta = no + dis
		if 0 <= resposta and resposta < n and (dist[resposta] == -1):
			dist[resposta] = dist[no] + 1
			fila.put(resposta)
	resposta = int(a[no]) - 1
	if dist[resposta] == -1:
		dist[resposta] = dist[no] + 1
		fila.put(resposta)
resposta_final = ''
for i in range(0, n):
	resposta_final += str(dist[i]) + ' '
print(resposta_final.strip(' '))


def solve(n, g):
	ans = [float('inf')] * (n + 1)
	ans[1] = 0
	q = [1]
	while q:
		t = q.pop(0)
		if t + 1 <= n and ans[t] + 1 < ans[t + 1]:
			ans[t + 1] = ans[t] + 1
			q.append(t + 1)
		if t - 1 >= 1 and ans[t] + 1 < ans[t - 1]:
			ans[t - 1] = ans[t] + 1
			q.append(t - 1)
		if ans[t] + 1 < ans[g[t]]:
			ans[g[t]] = ans[t] + 1
			q.append(g[t])
	return ans
n = int(input())
g = list(map(int, input().split()))
g.insert(0, 0)
ans = solve(n, g)
res = ' '.join([str(i) for i in ans[1:]])
print(res)


n_intersections = int(input())
shortcuts = list(map(int, input().split()))
shortcuts = [shortcut - 1 for shortcut in shortcuts]
costs = [0] + [-1] * (n_intersections - 1)
(i, queue) = (0, [0])
while i < len(queue):
	intersection = queue[i]
	shortcut = shortcuts[intersection]
	if costs[shortcut] == -1:
		costs[shortcut] = costs[intersection] + 1
		queue.append(shortcut)
	if intersection < n_intersections - 1:
		if costs[intersection + 1] == -1:
			costs[intersection + 1] = costs[intersection] + 1
			queue.append(intersection + 1)
	if intersection > 0:
		if costs[intersection - 1] == -1:
			costs[intersection - 1] = costs[intersection] + 1
			queue.append(intersection - 1)
	i += 1
print(' '.join(map(str, costs)))


from collections import deque
n = int(input())
a = list(map(int, input().split()))
dist = [-1 for i in range(n)]
bfs = deque()
bfs.append(0)
dist[0] = 0
while len(bfs):
	cur = bfs.popleft()
	for add in range(-1, 2):
		u = cur + add
		if 0 <= u and u < n and (dist[u] == -1):
			dist[u] = dist[cur] + 1
			bfs.append(u)
	u = a[cur] - 1
	if dist[u] == -1:
		dist[u] = dist[cur] + 1
		bfs.append(u)
print(*dist)


n = int(input())
x = [int(i) for i in input().split()]
y = [x[i] - 1 for i in range(n)]
q = [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([str(i) for i in res]))


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()


from collections import *
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)))


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])))


import queue
n = int(input())
a_list = list(map(int, input().split()))
used = []
d = []
for i in range(0, n):
	used.append(False)
	d.append(-1)
q = queue.Queue()
q.put(0)
d[0] = 0
while not q.empty():
	v = q.get()
	for dl in range(-1, 2):
		u = v + dl
		if 0 <= u and u < n and (d[u] == -1):
			d[u] = d[v] + 1
			q.put(u)
	u = a_list[v] - 1
	if d[u] == -1:
		d[u] = d[v] + 1
		q.put(u)
output = ''
for i in range(0, n):
	output += str(d[i]) + ' '
print(output)


from collections import deque

def bfs(start, graph):
	explored = set()
	queue = deque([start])
	levels = {}
	levels[start] = 0
	visited = {start}
	while queue:
		node = queue.popleft()
		explored.add(node)
		neighbours = graph[node]
		for neighbour in neighbours:
			if neighbour not in visited:
				queue.append(neighbour)
				visited.add(neighbour)
				levels[neighbour] = levels[node] + 1
	return levels
n = int(input())
l = list(map(int, input().split()))
graph = {}
for i in range(n):
	x = l[i]
	if i + 1 in graph:
		graph[i + 1].append(x)
	else:
		graph[i + 1] = [x]
	if i != n - 1:
		if i + 1 in graph:
			graph[i + 1].append(i + 2)
		else:
			graph[i + 1] = [i + 2]
		if i + 2 in graph:
			graph[i + 2].append(i + 1)
		else:
			graph[i + 2] = [i + 1]
e = bfs(1, graph)
ans = []
for i in range(1, n + 1):
	ans.append(e[i])
print(*ans)


n = int(input())
a = list(map(int, input().split()))
energy = [-1] * n
energy[0] = 0
pos = [0]
for i in pos:
	for v in [i - 1, i + 1, a[i] - 1]:
		if v >= 0 and v < n and (energy[v] == -1):
			energy[v] = energy[i] + 1
			pos.append(v)
print(*energy)


n = int(input())
Ais = list(map(int, input().split()))
Mis = [0] + [-1] * (n - 1)
pos = [0]
for i in pos:
	n1 = i - 1
	n2 = i + 1
	n3 = Ais[i] - 1
	for j in [n1, n2, n3]:
		if j >= 0 and j < n and (Mis[j] == -1):
			Mis[j] = Mis[i] + 1
			pos.append(j)
print(' '.join(map(str, Mis)))


import math
n = int(input())
cuts = list(map(int, input().split()))
cuts = [-1] + cuts
dist = [-1] * (n + 1)
dist[1] = 0
queue = [1]
while len(queue) > 0:
	v = queue.pop(0)
	if v + 1 <= n and dist[v + 1] == -1:
		dist[v + 1] = dist[v] + 1
		queue.append(v + 1)
	if dist[cuts[v]] == -1:
		dist[cuts[v]] = dist[v] + 1
		queue.append(cuts[v])
	if v - 1 > 0 and dist[v - 1] == -1:
		dist[v - 1] = dist[v] + 1
		queue.append(v - 1)
s = ' '.join(map(str, dist[1:]))
print(s)


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()


def amount_of_total_energy(n, a):
	dist = [-1] * n
	dist[0] = 0
	pos = [0]
	for u in pos:
		for v in [u - 1, u + 1, a[u] - 1]:
			if v >= 0 and v < n and (dist[v] == -1):
				dist[v] = dist[u] + 1
				pos.append(v)
	return dist
n = int(input())
a = list(map(int, input().split()))
print(*amount_of_total_energy(n, a))


def shortcuts(a):
	res = [0] + [10000000000.0 for i in range(1, len(a))]
	queue = [0]
	while queue != []:
		elem = queue.pop(0)
		c = res[elem]
		if elem + 1 < len(a) and c + 1 < res[elem + 1]:
			res[elem + 1] = c + 1
			queue.append(elem + 1)
		if elem - 1 >= 0 and c + 1 < res[elem - 1]:
			res[elem - 1] = c + 1
			queue.append(elem - 1)
		if c + 1 < res[a[elem] - 1]:
			res[a[elem] - 1] = c + 1
			queue.append(a[elem] - 1)
	return res
n = int(input())
a = [int(i) for i in input().split(' ')]
res = shortcuts(a)
from sys import stdout
for i in range(n):
	stdout.write(str(res[i]) + ' ')
print()


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)))


input_n = int(input())
shortcuts = list(map(int, input().split()))
shortcuts = [shortcuts[index] - 1 for index in range(input_n)]
result = [-1] * input_n
(result[0], index, f_array) = (0, 0, [0])
while index < len(f_array):
	found = f_array[index]
	index += 1
	if result[shortcuts[found]] == -1:
		result[shortcuts[found]] = result[found] + 1
		f_array.append(shortcuts[found])
	if found > 0 and result[found - 1] == -1:
		result[found - 1] = result[found] + 1
		f_array.append(found - 1)
	if found < input_n - 1 and result[found + 1] == -1:
		result[found + 1] = result[found] + 1
		f_array.append(found + 1)
print(*result)


n = int(input())
a = list(map(int, input().split()))
d = [-1] * n
d[0] = 0
p = [0]
for i in p:
	for j in [i - 1, i + 1, a[i] - 1]:
		if j >= 0 and j < n and (d[j] == -1):
			d[j] = d[i] + 1
			p.append(j)
print(*d)


import sys
import io, os
import math
gcd = math.gcd
sqrt = math.sqrt
ceil = math.ceil
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f

def check(x, arr, k):
	n = len(arr)
	mid = n // 2
	if x <= arr[mid]:
		return True
	c = 0
	for i in range(mid, n):
		c += max(0, x - arr[i])
	if c <= k:
		return True
	else:
		return False

def bfs(graph, root_node, no_of_nodes):
	st = root_node
	n = no_of_nodes
	q = [st]
	ptr = 0
	ans = [0] * n
	nv = [True] * n
	nv[st] = False
	while ptr != len(q):
		child = graph[q[ptr]]
		for i in range(len(child)):
			if nv[child[i]]:
				nv[child[i]] = False
				q.append(child[i])
				ans[child[i]] = 1 + ans[q[ptr]]
		ptr += 1
	return ans

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
		exit()
	if n == 2:
		print(0, 1)
		exit()
	for i in range(n):
		arr[i] -= 1
		if arr[i] == i:
			arr[i] = -1
	graph = [[] for i in range(n)]
	for i in range(n):
		if i - 1 > -1:
			graph[i].append(i - 1)
		if arr[i] > -1:
			graph[i].append(arr[i])
		if i + 1 < n:
			graph[i].append(i + 1)
	s = bfs(graph, 0, n)
	print(*s)
main()


n = int(input())
shortcuts = list(map(int, input().split()))
shortcuts = [shortcuts[i] - 1 for i in range(n)]
res = [-1] * n
(res[0], i) = (0, 0)
fList = [0]
while i < len(fList):
	temp = fList[i]
	i += 1
	if res[shortcuts[temp]] == -1:
		res[shortcuts[temp]] = res[temp] + 1
		fList.append(shortcuts[temp])
	if temp < n - 1 and res[temp + 1] == -1:
		res[temp + 1] = res[temp] + 1
		fList.append(temp + 1)
	if temp > 0 and res[temp - 1] == -1:
		res[temp - 1] = res[temp] + 1
		fList.append(temp - 1)
print(*res)


b = int(input())
c = list(map(int, input().split()))
c = [c1 - 1 for c1 in c]
(d, i, fila) = ([0] + [-1] * (b - 1), 0, [0])
while i < len(fila):
	a = fila[i]
	c1 = c[a]
	if d[c1] == -1:
		d[c1] = d[a] + 1
		fila.append(c1)
	if a < b - 1:
		if d[a + 1] == -1:
			d[a + 1] = d[a] + 1
			fila.append(a + 1)
	if a > 0:
		if d[a - 1] == -1:
			d[a - 1] = d[a] + 1
			fila.append(a - 1)
	i += 1
print(' '.join(map(str, d)))


import sys
input = sys.stdin.readline
from collections import deque

def bfs():
	q = deque([0])
	dist = [-1] * n
	dist[0] = 0
	while q:
		v = q.popleft()
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist
n = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(n)]
for i in range(n):
	if i + 1 < n:
		G[i].append(i + 1)
		G[i + 1].append(i)
	G[i].append(a[i] - 1)
print(*bfs())


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)
main()


def solution(shortcuts, n):
	visited = [-1] * n
	queue = [0]
	visited[0] = 0
	while len(queue):
		node = queue.pop(0)
		for i in [-1, 0, 1]:
			c = node + i
			if c >= 0 and c < n and (visited[c] == -1):
				visited[c] = visited[node] + 1
				queue.append(c)
		c = shortcuts[node] - 1
		if visited[c] == -1:
			queue.append(c)
			visited[c] = visited[node] + 1
	return visited
n = int(input())
shortcuts = list(map(int, input().split()))
result = solution(shortcuts, n)
print(*result, sep=' ')


n = int(input())
a = list(map(int, input().split()))
dist = [-1] * n
dist[0] = 0
pos = [0]
for i in pos:
	for j in [i - 1, i + 1, a[i] - 1]:
		if j >= 0 and j < n and (dist[j] == -1):
			dist[j] = dist[i] + 1
			pos.append(j)
print(*dist)


def bfs(nCruzamentos, cruzamentos, aux, fila):
	while len(fila) > 0:
		atual = fila.pop(0)
		if atual < nCruzamentos and aux[atual + 1] > aux[atual] + 1:
			aux[atual + 1] = aux[atual] + 1
			fila.append(atual + 1)
		if atual > 1 and aux[atual - 1] > aux[atual] + 1:
			aux[atual - 1] = aux[atual] + 1
			fila.append(atual - 1)
		if aux[cruzamentos[atual]] > aux[atual] + 1:
			aux[cruzamentos[atual]] = aux[atual] + 1
			fila.append(cruzamentos[atual])

def mikeAndShortcuts(nCruzamentos, atalhos):
	cruzamentos = [0] + [int(x) for x in atalhos]
	aux = [float('inf') for x in range(nCruzamentos + 1)]
	aux[1] = 0
	fila = [1]
	bfs(nCruzamentos, cruzamentos, aux, fila)
	print(' '.join((str(i) for i in aux[1:])))
nCruzamentos = int(input())
atalhos = input().split()
mikeAndShortcuts(nCruzamentos, atalhos)


from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(num_vert, graph):
	dist = [9999999999] * num_vert
	dist[0] = 0
	h = [0]
	heappush(h, 0)
	while h:
		v = heappop(h)
		for e in graph[v]:
			if dist[e] > dist[v] + 1:
				dist[e] = dist[v] + 1
				heappush(h, e)
	print(' '.join([str(int) for int in dist]))
n = int(input())
shortcuts = list(map(int, input().split()))
graph = defaultdict(set)
for i in range(n):
	if i != 0:
		graph[i].add(i - 1)
	if i < n - 1:
		graph[i].add(i + 1)
	if shortcuts[i] - 1 != i:
		graph[i].add(shortcuts[i] - 1)
dijkstra(n, graph)


n = int(input())
a = list(map(int, input().split()))
res = n * [-1]
res[0] = 0
pos = [0]
for i in pos:
	for j in [i - 1, i + 1, a[i] - 1]:
		if j >= 0 and j < n:
			if res[j] == -1:
				res[j] = res[i] + 1
				pos.append(j)
print(' '.join(map(str, res)))


n = int(input())
a = list(map(int, input().split()))
distances = [-1] * n
distances[0] = 0
positions = [0]
for u in positions:
	for v in [u - 1, u + 1, a[u] - 1]:
		if v >= 0 and v < n and (distances[v] == -1):
			distances[v] = distances[u] + 1
			positions.append(v)
print(*distances)


num = int(input())
shortcuts = list(map(int, input().split()))
shortcuts = [shortcuts[i] - 1 for i in range(num)]
result = [-1] * num
(result[0], i, array) = (0, 0, [0])
while i < len(array):
	found = array[i]
	i += 1
	if result[shortcuts[found]] == -1:
		result[shortcuts[found]] = result[found] + 1
		array.append(shortcuts[found])
	if found > 0 and result[found - 1] == -1:
		result[found - 1] = result[found] + 1
		array.append(found - 1)
	if found < num - 1 and result[found + 1] == -1:
		result[found + 1] = result[found] + 1
		array.append(found + 1)
print(*result)


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 = list(map(int, input().split()))
for i in range(n):
	A[i] -= 1
dist = [-1 for i in range(n)]
dist[0] = 0
Q = [0]
while len(Q) != 0:
	k = 0
	u = Q.pop(0)
	if dist[A[u]] == -1:
		dist[A[u]] = dist[u] + 1
		k += 1
		if A[u] not in Q:
			Q.append(A[u])
	elif dist[A[u]] > dist[u] + 1:
		dist[A[u]] = dist[u] + 1
		k += 1
		if A[u] not in Q:
			Q.append(A[u])
	for v in range(u - 1, u + 2):
		if v < 0 or v >= n:
			continue
		if dist[v] == -1:
			dist[v] = dist[u] + abs(u - v)
			if v not in Q:
				Q.append(v)
		elif dist[u] + abs(u - v) < dist[v]:
			dist[v] = dist[u] + abs(u - v)
			k += 1
			if v not in Q:
				Q.append(v)
print(' '.join(map(str, dist)))


import heapq
from collections import defaultdict
cache = defaultdict(lambda : float('inf'))
visited = set()
visited.add(1)

def find():
	heap = [(0, 1)]
	while heap:
		(cost, city) = heapq.heappop(heap)
		if city <= 0 or city >= len(a):
			continue
		visited.add(city)
		cache[city] = min(cache[city], cost)
		for n in [city + 1, city - 1, a[city]]:
			if n not in visited:
				c = abs(n - city) if n != a[city] else 1
				if cache[n] > cost + c:
					heapq.heappush(heap, (cost + c, n))
					cache[n] = cost + c
n = int(input())
nebs = [i for i in range(1, n + 1)]
a = [-1] + [int(i) for i in input().split()]
res = []
find()
for i in range(1, n + 1):
	res.append(str(cache[i]))
print(' '.join(res))


n = int(input())
entrada = list(map(int, input().split()))
entrada = [0] + entrada
distancia = [float('inf') for x in range(n + 1)]
distancia[1] = 0
pilha = [1]
while len(pilha) > 0:
	dist = pilha[0]
	pilha = pilha[1:]
	if dist < n and distancia[dist + 1] > distancia[dist] + 1:
		distancia[dist + 1] = distancia[dist] + 1
		pilha += [dist + 1]
	if dist > 1 and distancia[dist - 1] > distancia[dist] + 1:
		distancia[dist - 1] = distancia[dist] + 1
		pilha += [dist - 1]
	if distancia[entrada[dist]] > distancia[dist] + 1:
		distancia[entrada[dist]] = distancia[dist] + 1
		pilha += [entrada[dist]]
distancia = distancia[1:]
print(' '.join(list(map(str, distancia))))


import queue

def create_int_list(n):
	l = []
	for i in range(0, n):
		l.append(-1)
	return l
n = int(input())
atalhos = [0] + [int(x) for x in input().split()]
distancias = create_int_list(n + 1)
fila = queue.Queue()
distancias[1] = 0
fila.put(1)
while fila.qsize() > 0:
	k = fila.get()
	if k + 1 <= n and distancias[k + 1] == -1:
		distancias[k + 1] = distancias[k] + 1
		fila.put(k + 1)
	if distancias[atalhos[k]] == -1:
		distancias[atalhos[k]] = distancias[k] + 1
		fila.put(atalhos[k])
	if k - 1 > 0 and distancias[k - 1] == -1:
		distancias[k - 1] = distancias[k] + 1
		fila.put(k - 1)
for i in range(1, n + 1):
	print('%d ' % distancias[i], end='')


n = int(input())
a = list(map(int, input().split()))
dist = [-1] * n
dist[0] = 0
pos = [0]
for u in pos:
	for v in [u - 1, u + 1, a[u] - 1]:
		if v >= 0 and v < n and (dist[v] == -1):
			dist[v] = dist[u] + 1
			pos.append(v)
print(' '.join(map(str, dist)))


from queue import Queue

def bfs(vertice):
	q = Queue()
	q.put(vertice)
	dist[vertice] = 0
	while not q.empty():
		v = q.get()
		for vizinho in adj[v]:
			if dist[vizinho] > dist[v] + 1:
				dist[vizinho] = dist[v] + 1
				q.put(vizinho)
INF = 10 ** 9
n = int(input())
adj = [0]
adj.extend([int(x) for x in input().split()])
dist = [INF] * (n + 1)
for i in range(1, n + 1):
	adj[i] = [adj[i]]
	if i != 1:
		adj[i].append(i - 1)
	if i != n:
		adj[i].append(i + 1)
bfs(1)
result = ''
for i in range(1, len(dist)):
	result += str(dist[i]) + ' '
print(result)


from sys import stdin, stdout, stderr
import queue

def main():
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	d = [10000000 for i in range(n)]
	g = [[i - 1, i + 1] for i in range(n)]
	g[0] = [1]
	g[n - 1] = [n - 2]
	d[0] = 0
	for i in range(n):
		if a[i] == i + 1:
			continue
		g[i].append(a[i] - 1)
	q = queue.Queue()
	q.put_nowait(0)
	while not q.empty():
		x = q.get_nowait()
		for to in g[x]:
			if d[x] + 1 < d[to]:
				d[to] = d[x] + 1
				q.put_nowait(to)
	for x in d:
		stdout.write(str(x) + ' ')
main()


import queue
n = int(input())
cruzamentos = list(map(int, input().split()))
energia = []
for i in range(0, n):
	energia.append(-1)
aux = queue.Queue()
aux.put(0)
energia[0] = 0
while not aux.empty():
	v = aux.get()
	for i in range(-1, +2):
		u = v + i
		if 0 <= u and u < n and (energia[u] == -1):
			energia[u] = energia[v] + 1
			aux.put(u)
	u = cruzamentos[v] - 1
	if energia[u] == -1:
		energia[u] = energia[v] + 1
		aux.put(u)
print(' '.join(list(map(str, energia))))


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=' ')


n = int(input())
a = [int(i) - 1 for i in input().split()]
m = [-1] * len(a)
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 queue
n = int(input())
a = [0] + list(map(int, input().split()))
q = queue.Queue()
d = [n for i in range(n + 1)]
d[1] = 0
q.put(1)
while q.empty() == False:
	top = q.get()
	if top + 1 <= n:
		if d[top + 1] > d[top] + 1:
			d[top + 1] = d[top] + 1
			q.put(top + 1)
	if top - 1 >= 1:
		if d[top - 1] > d[top] + 1:
			d[top - 1] = d[top] + 1
			q.put(top - 1)
	if d[a[top]] > d[top] + 1:
		d[a[top]] = d[top] + 1
		q.put(a[top])
for i in range(1, n + 1):
	print(d[i], end=' ')


n = int(input())
shortcuts = list(map(int, input().split()))
shortcuts = [shortcuts[i] - 1 for i in range(n)]
result = [-1] * n
result[0] = 0
lista = [0]
i = 0
while i < len(lista):
	j = lista[i]
	i += 1
	if result[shortcuts[j]] == -1:
		result[shortcuts[j]] = result[j] + 1
		lista.append(shortcuts[j])
	if j > 0 and result[j - 1] == -1:
		result[j - 1] = result[j] + 1
		lista.append(j - 1)
	if j < n - 1 and result[j + 1] == -1:
		result[j + 1] = result[j] + 1
		lista.append(j + 1)
print(*result)


from queue import Queue
q = Queue()
n = int(input())
a = list(map(int, input().split()))
used = [-1] * n
q.put(0)
while not q.empty():
	v = q.get()
	if used[v] == -1:
		used[v] = 0
	if 0 <= v < n - 1 and used[v + 1] == -1:
		used[v + 1] = used[v] + 1
		q.put(v + 1)
	if 0 < v < n and used[v - 1] == -1:
		used[v - 1] = used[v] + 1
		q.put(v - 1)
	u = a[v] - 1
	if used[u] == -1:
		used[u] = used[v] + 1
		q.put(u)
print(*used)


def mike_shortcuts(queue, res):
	index = 0
	while index < len(queue):
		queue_element = queue[index]
		if res[entry[queue_element]] == -1:
			res[entry[queue_element]] = res[queue_element] + 1
			queue.append(entry[queue_element])
		if queue_element < n - 1 and res[queue_element + 1] == -1:
			res[queue_element + 1] = res[queue_element] + 1
			queue.append(queue_element + 1)
		if queue_element > 0 and res[queue_element - 1] == -1:
			res[queue_element - 1] = res[queue_element] + 1
			queue.append(queue_element - 1)
		index += 1
	return res
n = int(input())
entry = [int(index) - 1 for index in input().split(' ')]
res = mike_shortcuts([0], [0] + [-1] * (n - 1))
print(' '.join((str(x) for x in res)))


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())
Ais = list(map(int, input().split()))
Mis = [0] + [-1] * (n - 1)
pos = [0]
for i in pos:
	a = i - 1
	b = i + 1
	c = Ais[i] - 1
	for j in [a, b, c]:
		if j >= 0 and j < n and (Mis[j] == -1):
			Mis[j] = Mis[i] + 1
			pos.append(j)
print(' '.join(map(str, Mis)))


def bfs():
	while len(queue) > 0:
		current = queue.pop(0)
		if current < n and dis[current + 1] > dis[current] + 1:
			dis[current + 1] = dis[current] + 1
			queue.append(current + 1)
		if current > 1 and dis[current - 1] > dis[current] + 1:
			dis[current - 1] = dis[current] + 1
			queue.append(current - 1)
		if dis[shortlist[current]] > dis[current] + 1:
			dis[shortlist[current]] = dis[current] + 1
			queue.append(shortlist[current])
n = int(input())
input2 = input().split()
shortlist = [0] + [int(x) for x in input2]
dis = [float('inf') for x in range(n + 1)]
dis[1] = 0
queue = [1]
bfs()
print(' '.join((str(i) for i in dis[1:])))


n = int(input())
a = list(map(int, input().split()))
distancia = [-1] * n
distancia[0] = 0
posicao = [0]
for i in posicao:
	for j in [i - 1, i + 1, a[i] - 1]:
		if j >= 0 and j < n and (distancia[j] == -1):
			distancia[j] = distancia[i] + 1
			posicao.append(j)
print(*distancia)


def solve(N, nums):
	ans = [float('inf')] * N
	ans[0] = str(0)
	for i in range(N):
		v = nums[i]
		nums[i] = set([min(N - 1, i + 1), max(0, i - 1), v - 1])
	d = 0
	q = set([0])
	while q:
		next_q = set()
		d += 1
		for node in q:
			for next_node in nums[node]:
				if ans[next_node] == float('inf'):
					ans[next_node] = str(d)
					next_q.add(next_node)
		q = next_q
	return ans
N = int(input())
nums = list(map(int, input().split()))
ans = solve(N, nums)
print(' '.join(ans))


from collections import deque
n = int(input())
a = list(map(int, input().split()))
result = len(a) * [-1]
for i in range(len(a)):
	a[i] -= 1
result[0] = 0
q = deque()
q.appendleft(0)
while len(q) > 0:
	u = q.pop()
	l = [a[u], u + 1, u - 1]
	for v in l:
		if v < 0 or v >= n:
			continue
		if result[v] == -1:
			result[v] = result[u] + 1
			q.appendleft(v)
print(' '.join(list(map(str, result))))


from queue import Queue
n = int(input())
shortcuts = list(map(int, input().split(' ')))
d = [-1 for _ in range(0, n)]
queue = Queue()
queue.put(0)
d[0] = 0
while not queue.empty():
	v = queue.get()
	for dl in range(-1, 2):
		u = v + dl
		if 0 <= u and u < n and (d[u] == -1):
			d[u] = d[v] + 1
			queue.put(u)
	u = shortcuts[v] - 1
	if d[u] == -1:
		d[u] = d[v] + 1
		queue.put(u)
print(' '.join(map(str, [d[i] for i in range(0, n)])))


n = a = None

def entrypoint():
	global n, a
	n = int(input())
	a = list(map(int, input().split()))

def process():
	for i in range(n):
		a[i] -= 1
		if a[i] <= i + 1:
			a[i] = None
	m = [-1] * n
	m[0] = 0
	current = [0]
	val_next = []
	while True:
		if current:
			for i in current:
				x = m[i] + 1
				if a[i] and m[a[i]] == -1:
					m[a[i]] = x
					val_next.append(a[i])
				if i != 0 and m[i - 1] == -1:
					m[i - 1] = x
					val_next.append(i - 1)
				if i != n - 1 and m[i + 1] == -1:
					m[i + 1] = x
					val_next.append(i + 1)
			current = val_next
			val_next = []
		else:
			break
	print(' '.join(map(str, m)))

def main():
	entrypoint()
	process()
main()


import queue
n = int(input())
m = input().split(' ')
usado = []
a = []
for i in range(0, n):
	usado.append(False)
	a.append(-1)
q = queue.Queue()
q.put(0)
a[0] = 0
while not q.empty():
	valor = q.get()
	for dl in range(-1, +2):
		u = valor + dl
		if 0 <= u and u < n and (a[u] == -1):
			a[u] = a[valor] + 1
			q.put(u)
	u = int(m[valor]) - 1
	if a[u] == -1:
		a[u] = a[valor] + 1
		q.put(u)
for i in range(0, n):
	print(a[i])


n = int(input())
res = [0] + [n for i in range(n)]
k = [[i + 1, i - 1] if i < n else [i - 1] for i in range(0, n + 1)]
(k[0], res[1]) = ([], 0)
for (i, x) in enumerate(map(int, input().split())):
	if i + 1 != x:
		k[i + 1] += [x]
chill = [(0, 1)]
while chill:
	(l, j) = chill.pop(0)
	for x in k[j]:
		if l + 1 < res[x]:
			res[x] = l + 1
			chill.append((l + 1, x))
print(*res[1:])


from sys import stdin, stdout
(readline, writeline) = (stdin.readline, stdout.write)
n = int(readline().strip())
s = list(map(int, readline().strip().split()))
ans = [0] + [200001] * (n - 1)
for i in range(n):
	ans[i] = min(ans[i], ans[i - 1] + 1)
	j = i
	if j + 1 < n:
		while ans[j + 1] + 1 < ans[j]:
			ans[j] = ans[j + 1] + 1
			ans[s[j] - 1] = min(ans[s[j] - 1], ans[j] + 1)
			j -= 1
	ans[s[i] - 1] = min(ans[s[i] - 1], ans[i] + 1)
for i in range(n):
	writeline('{} '.format(ans[i]))
writeline('\n')


import sys
input = sys.stdin.readline
from collections import deque
t = 1
import math

def bfs(a, i, dis, vis):
	vis[i] = 1
	pp = deque()
	pp.append(i)
	while len(pp) != 0:
		z = pp[0]
		vis[z] = 1
		pp.popleft()
		for j in a[z]:
			if vis[j] == 0:
				vis[j] = 1
				dis[j] = min(dis[j], dis[z] + 1)
				pp.append(j)
while t > 0:
	t -= 1
	n = int(input())
	b = [int(x) for x in input().split()]
	a = [[] for i in range(n + 1)]
	for i in range(n):
		x = i + 1
		y = b[i]
		if i != n - 1:
			a[i + 1].append(i + 2)
		if i != 0:
			a[i + 1].append(i)
		if x == y:
			continue
		a[x].append(y)
	vis = [0 for i in range(n + 1)]
	dis = [i - 1 for i in range(n + 1)]
	bfs(a, 1, dis, vis)
	for i in range(1, n):
		dis[i + 1] = min(dis[i + 1], dis[i] + 1)
	print(*dis[1:])


n = int(input())
shortest_path = list(map(int, input().split()))
shortest_path = [shortest_path[i] - 1 for i in range(n)]
result = [-1] * n
result[0] = 0
i = 0
aux = [0]
while i < len(aux):
	temp = aux[i]
	i += 1
	if result[shortest_path[temp]] == -1:
		result[shortest_path[temp]] = result[temp] + 1
		aux.append(shortest_path[temp])
	if temp < n - 1 and result[temp + 1] == -1:
		result[temp + 1] = result[temp] + 1
		aux.append(temp + 1)
	if temp > 0 and result[temp - 1] == -1:
		result[temp - 1] = result[temp] + 1
		aux.append(temp - 1)
print(*result)


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])


n = int(input())
arr = list(map(int, input().split()))
arr = [q - 1 for q in arr]
dist = [0] + [-1] * (n - 1)
i = 0
queue = [0]
while i < len(queue):
	k = queue[i]
	q = arr[k]
	if dist[q] == -1:
		dist[q] = dist[k] + 1
		queue.append(q)
	if k < n - 1 and dist[k + 1] == -1:
		dist[k + 1] = dist[k] + 1
		queue.append(k + 1)
	if k > 0 and dist[k - 1] == -1:
		dist[k - 1] = dist[k] + 1
		queue.append(k - 1)
	i += 1
print(' '.join((str(e) for e in dist)))


from sys import stdin, stdout
from collections import deque
(read, write) = (stdin.readline, stdout.write)
n = int(read())
shortcuts = list(map(lambda x: int(x) - 1, read().split()))
graph = [[] for _ in range(n)]
for i in range(n):
	graph[i] = list({max(0, i - 1), min(n - 1, i + 1), shortcuts[i]})
queue = deque([(0, 0)])
visited = [0] * n
distances = [float('inf')] * n
(visited[0], distances[0]) = (1, 0)
while queue:
	(node, distance) = queue.popleft()
	for neighbor in graph[node]:
		if not visited[neighbor]:
			queue.append((neighbor, distance + 1))
			distances[neighbor] = distance + 1
			visited[neighbor] = 1
write(' '.join(map(str, distances)))


def calcEnergy(seq, energy, stcs):
	j = 0
	while j < len(seq):
		elem = seq[j]
		if energy[stcs[elem]] == -1:
			energy[stcs[elem]] = energy[elem] + 1
			seq.append(stcs[elem])
		if elem < intersection - 1 and energy[elem + 1] == -1:
			energy[elem + 1] = energy[elem] + 1
			seq.append(elem + 1)
		if elem > 0 and energy[elem - 1] == -1:
			energy[elem - 1] = energy[elem] + 1
			seq.append(elem - 1)
		j += 1
	return energy
intersection = int(input())
stcs = [int(i) - 1 for i in input().split(' ')]
energy = calcEnergy([0], [0] + [-1] * (intersection - 1), stcs)
leastTotalOfEnergy = ' '.join((str(x) for x in energy))
print(leastTotalOfEnergy)


from queue import Queue
n = int(input())
shortcuts = [int(nb) for nb in input().split()]
dst = [-1] * n
dst[0] = 0
q = Queue()
q.put(0)
while not q.empty():
	node = q.get()
	for u in [node - 1, node + 1, shortcuts[node] - 1]:
		if 0 <= u and u < n and (dst[u] == -1):
			dst[u] = dst[node] + 1
			q.put(u)
for i in range(len(dst)):
	print(dst[i], end=' ')


import queue
dimension = 2000000
maxValue = 1e+20
num_intersections = int(input())
shortcuts = [0] + list(map(int, input().split())) + [maxValue] * dimension
amount_energy = [maxValue] * dimension
q = queue.Queue()
amount_energy[1] = 0
q.put(1)
while q.qsize():
	k = q.get()
	if k != num_intersections and amount_energy[k + 1] > amount_energy[k] + 1:
		amount_energy[k + 1] = amount_energy[k] + 1
		q.put(k + 1)
	if k != 1 and amount_energy[k - 1] > amount_energy[k] + 1:
		amount_energy[k - 1] = amount_energy[k] + 1
		q.put(k - 1)
	if amount_energy[shortcuts[k]] > amount_energy[k] + 1:
		amount_energy[shortcuts[k]] = amount_energy[k] + 1
		q.put(shortcuts[k])
for i in range(1, num_intersections + 1):
	print(amount_energy[i], end=' ')


import queue
n = int(input())
entry = list(map(int, input().split()))
energy = [-1] * n
q = queue.Queue()
q.put(0)
energy[0] = 0
while not q.empty():
	v = q.get()
	for dl in range(-1, +2):
		u = v + dl
		if 0 <= u and u < n and (energy[u] == -1):
			energy[u] = energy[v] + 1
			q.put(u)
	u = entry[v] - 1
	if energy[u] == -1:
		energy[u] = energy[v] + 1
		q.put(u)
output = ''
for i in range(0, n):
	output += str(energy[i]) + ' '
print(output)


n = int(input())
a = list(map(int, input().split()))
distance = [-1] * n
distance[0] = 0
positions = [0]
for i in positions:
	for j in [i - 1, i + 1, a[i] - 1]:
		if j >= 0 and j < n and (distance[j] == -1):
			distance[j] = distance[i] + 1
			positions.append(j)
print(*distance)