CF689B Mike and Shortcuts

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\limits_{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

The first line contains an integer $ n $ $ (1

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 $ .

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$ 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 $ .