Ildar是William和Harris的算法老师。今天,伊尔达正在教授笛卡尔树。然而,哈里斯生病了,所以伊尔达只教威廉。
笛卡尔树是一棵有根树,可以由一系列不同的整数构成。我们按如下方式构建笛卡尔树:
1.如果序列为空,则返回空树;
2、设最大元素的位置为$$$x$$$;
3.从序列中删除$$$x$$$位置上的元素,并将其分成左右部分(可能是空的)(不是真正删除,只是暂时拿走);
4.为每个部分构建笛卡尔树;
5. 为元素创建一个新顶点,该顶点位于 $$$x$$$ 位置,它将作为新树的根。然后,对于左部分和右部分的根,如果存在,将成为该顶点的子节点;
6. 返回我们得到的树。
例如,这是序列 $$$4, 2, 7, 3, 5, 6, 1$$$ 的笛卡尔树:
教完笛卡尔树是什么后,Ildar 布置了作业。他从一个空序列 $$$a$$$ 开始。
在第 $$$i$$$ 轮中,他在 $$$a$$$ 中的某处插入了一个值为 $$$i$$$ 的元素。然后,他提出一个问题:当前序列 $$$a$$$ 的笛卡尔树中每个节点的子树大小之和是多少?
节点 $$$v$$$ 位于节点 $$$u$$$ 子树中当且仅当 $$$v = u$$$ 或 $$$v$$$ 位于节点 $$$u$$$ 子节点之一的子树中。节点$$$u$$$的子树的大小是使得$$$v$$$位于$$$u$$$的子树中的节点$$$v$$$的数量。
Ildar 总共将进行 $$$n$$$ 轮。家庭作业是对 $$$n$$$ 问题的回答序列。
第二天,伊尔达告诉哈里斯他也必须完成作业。哈里斯从威廉那里获得了序列 $$$a$$$ 的最终状态。然而,他不知道如何找到 $$$n$$$ 问题的答案。帮助哈里斯!
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 150000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。保证从 $$$1$$$ 到 $$$n$$$ 的每个整数在序列中只出现一次。
输出
打印 $$$n$$$ 行,第 $$$i$$$ 行应包含一个整数 - 第 $$$i$$$ 问题的答案。
示例
输入 #1
5 2 4 1 5 3
输出 #1
1 3 6 8 11
输入 #2
6 1 2 4 5 6 3
输出 #2
1 3 6 8 12 17
注意
第一轮结束后,顺序是$$$1$$$。这棵树是
答案是$$$1$$$。
第二轮结束后,顺序是$$$2, 1$$$。这棵树是
答案是$$$2+1=3$$$。
第三轮结束后,顺序是$$$2, 1, 3$$$。这棵树是
答案是$$$2+1+3=6$$$。
第四轮结束后,顺序是$$$2, 4, 1, 3$$$。这棵树是
答案是$$$1+4+1+2=8$$$。
第五轮结束后,顺序是$$$2, 4, 1, 5, 3$$$。这棵树是
答案是$$$1+3+1+5+1=11$$$。