markdown

E. 笛卡尔树

时间限制：每个测试点 $5$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

Ildar 是 William 和 Harris 的算法老师。今天，Ildar 正在讲解笛卡尔树。不过 Harris 生病了，所以只有 William 在上课。

笛卡尔树是一棵有根树，可以由一个由互不相同的整数构成的序列构造而成。构造方法如下：

• 如果序列为空，则返回一棵空树；
• 设最大元素的位置为 $p$；
• 将位置 $p$ 上的元素从序列中移除（只是临时取出，并非真正删除），并将原序列分成左半部分和右半部分（可能为空）；
• 分别对左、右两部分递归构建笛卡尔树；
• 为位置 $p$ 上的元素创建一个新结点，作为新树的根。如果左、右两部分构造出的树根存在，则它们成为该结点的子结点；
• 返回构造好的树。

例如，对于序列 $[1,2,7,3,5,6,4]$，其笛卡尔树如下所示：

（此处应有图片，但文本中省略）

讲完笛卡尔树的定义后，Ildar 布置了作业。他首先有一个空序列 $S$。

在第 $i$ 轮中，他将一个值为 $a_i$ 的元素插入到 $S$ 的某个位置。然后，他提出一个问题：对于当前序列 $S$ 所对应的笛卡尔树，所有结点的子树大小之和是多少？

结点 $u$ 在结点 $v$ 的子树中，当且仅当 $u = v$ 或 $u$ 在 $v$ 的某个子结点的子树中。结点 $v$ 的子树大小是指满足“$u$ 在 $v$ 的子树中”的结点 $u$ 的个数。

Ildar 总共会进行 $n$ 轮。作业就是这 $n$ 个问题的答案序列。

第二天，Ildar 告诉 Harris 他也必须完成这份作业。Harris 从 William 那里得到了序列 $S$ 的最终状态，但他不知道如何求出这 $n$ 个问题的答案。请帮助 Harris！

输入

第一行包含一个整数 $n$（$1 \le n \le 150000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, 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

注释

• 第一轮后，序列为 $[2]$。对应的树只有一个结点，答案为 $1$。
• 第二轮后，序列为 $[2,1]$。对应的树中，结点 $2$ 的子树大小为 $2$，结点 $1$ 的子树大小为 $1$，答案为 $2+1=3$。
• 第三轮后，序列为 $[2,1,3]$。对应的树中，结点 $2$ 的子树大小为 $3$，结点 $1$ 的子树大小为 $1$，结点 $3$ 的子树大小为 $2$，答案为 $3+1+2=6$。
• 第四轮后，序列为 $[2,4,1,3]$。对应的树中，结点 $2$ 的子树大小为 $4$，结点 $4$ 的子树大小为 $1$，结点 $1$ 的子树大小为 $2$，结点 $3$ 的子树大小为 $1$，答案为 $4+1+2+1=8$。
• 第五轮后，序列为 $[2,4,1,5,3]$。对应的树中，结点 $2$ 的子树大小为 $5$，结点 $4$ 的子树大小为 $3$，结点 $1$ 的子树大小为 $1$，结点 $5$ 的子树大小为 $1$，结点 $3$ 的子树大小为 $1$，答案为 $5+3+1+1+1=11$。