题目描述

       Freda想给Rainbow写一封信邀请Ta参观花园,但是又害怕大坏蛋whitetooth知道信函的内容,因此,Freda需要把这封信加密。信函其实是一张立体花园的建造图。花园由N个小园子组成,Freda希望按照如下的建造流程建造:(看不懂花园的结构可以想象一下二叉排序树
       1、给这N个园子编号为1~N
       2、找一个园子作为整个花园的入口 
       3、找一个还没有被安排位置的园子a.
       4、从入口开始,设当前到达的园子编号为b.
       如果a<b:
              若b的左下方没有隧道,就把a安排在b的左下方距离为1的位置,并在a和b之间设一条隧道
              若b的左下方已有隧道,那么将b设为其左下方距离为1的那个园子编号
       如果a>b(我们知道a一定不等于b):
              若b的右下方没有隧道,就把a安排在b的右下方距离为1的位置,并在a和b之间设一条隧道
              若b的右下方已有隧道,那么将b设为其右下方距离为1的那个园子编号
       重复此步骤直到园子a被安排了位置
       5、如果还有没有被安排位置的园子,返回第3步
       显然,按照这个操作流程,所有园子一定都能被安排位置。Freda想让Rainbow帮忙看一下这个方案是否可行,但是又怕whitetooth窃取机密。因此,Freda给你整个花园入口的编号以及园子被安排位置的顺序,请你帮Rainbow在每次安排园子位置之后,输出所有园子与花园入口的距离之和。

输入格式

第一行一个整数N,表示花园中小园子的个数。
接下来N行每行一个整数,其中第2行的整数表示花园入口的园子编号,第3~N+1行按顺序表示园子被安排位置的顺序。

输出格式

N行,每行一个整数。第i行的整数表示Freda安排顺序中第i个园子(包括入口)被安排位置后,所有园子与入口的距离之和。

样例输入

4
3
2
4
1

样例输出

0
1
2
4

样例解释

3被安排在入口位置,此时ans=dist(3,3)=0
2被安排在3左下距离为1的位置,此时ans=dist(3,3)+dist(2,3)=0+1=1
4被安排在3右下距离为1的位置,此时ans=dist(3,3)+dist(2,3)+dist(4,3)=0+1+1=2
1被安排在2左下距离为1的位置,此时ans=dist(3,3)+dist(2,3)+dist(4,3)+dist(1,3)=0+1+1+2=4

数据范围与约定

对于20%的数据,N<=1000
对于30%的数据,保证数据随机。
对于100%的数据,1<=N<=300000