CF1290E.Cartesian Tree

Ildar is the algorithm teacher of William and Harris. Today, Ildar is teaching Cartesian Tree. However, Harris is sick, so Ildar is only teaching William.

A cartesian tree is a rooted tree, that can be constructed from a sequence of distinct integers. We build the cartesian tree as follows:

1. If the sequence is empty, return an empty tree;
2. Let the position of the maximum element be $x$;
3. Remove element on the position $x$ from the sequence and break it into the left part and the right part (which might be empty) (not actually removing it, just taking it away temporarily);
4. Build cartesian tree for each part;
5. Create a new vertex for the element, that was on the position $x$ which will serve as the root of the new tree. Then, for the root of the left part and right part, if exists, will become the children for this vertex;
6. Return the tree we have gotten.

For example, this is the cartesian tree for the sequence $4, 2, 7, 3, 5, 6, 1$:

After teaching what the cartesian tree is, Ildar has assigned homework. He starts with an empty sequence $a$.

In the $i$-th round, he inserts an element with value $i$ somewhere in $a$. Then, he asks a question: what is the sum of the sizes of the subtrees for every node in the cartesian tree for the current sequence $a$?

Node $v$ is in the node $u$ subtree if and only if $v = u$ or $v$ is in the subtree of one of the vertex $u$ children. The size of the subtree of node $u$ is the number of nodes $v$ such that $v$ is in the subtree of $u$.

Ildar will do $n$ rounds in total. The homework is the sequence of answers to the $n$ questions.

The next day, Ildar told Harris that he has to complete the homework as well. Harris obtained the final state of the sequence $a$ from William. However, he has no idea how to find the answers to the $n$ questions. Help Harris!

伊尔达尔是威廉和哈里斯的算法老师。今天，伊尔达尔正在讲授笛卡尔树（Cartesian Tree）。然而，哈里斯生病了，因此伊尔达尔只给威廉授课。

笛卡尔树是一种有根树，可由一个互不相同的整数序列构造而成。其构造过程如下：

1. 若序列为空，则返回一棵空树；
2. 设最大元素的位置为 $x$；
3. 将位置 $x$ 上的元素从序列中移除，并将序列分割为左部分和右部分（这两部分可能为空）（注意：此处并非真正删除该元素，而只是暂时将其取走）；
4. 分别对左部分和右部分递归构造笛卡尔树；
5. 为原位置 $x$ 上的元素新建一个结点，作为新树的根；若左部分和右部分对应的子树根存在，则分别成为该新根的左右子结点；
6. 返回所得到的树。

例如，序列 $4, 2, 7, 3, 5, 6, 1$ 对应的笛卡尔树如下所示：

在讲解完笛卡尔树的定义后，伊尔达尔布置了课后作业。他从一个空序列 $a$ 开始。

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

当且仅当 $v = u$ 或 $v$ 位于 $u$ 的某个子结点的子树中时，称结点 $v$ 属于结点 $u$ 的子树。结点 $u$ 的子树大小，即为其子树中所有结点 $v$ 的数量。

伊尔达尔总共进行 $n$ 轮操作。该作业的答案即为这 $n$ 次提问所对应的 $n$ 个答案所组成的序列。

第二天，伊尔达尔告诉哈里斯，他也必须完成这份作业。哈里斯已从威廉处获得了序列 $a$ 的最终状态。但他完全不知道如何求出这 $n$ 个问题的答案。请帮助哈里斯！

The first line contains a single integer $n$ ($1 \le n \le 150000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guarenteed that each integer from $1$ to $n$ appears in the sequence exactly once.

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

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。保证 $1$ 到 $n$ 中的每个整数在序列中恰好出现一次。

Print $n$ lines, $i$-th line should contain a single integer — the answer to the $i$-th question.

输出 $n$ 行，第 $i$ 行应包含一个整数——即第 $i$ 个问题的答案。

After the first round, the sequence is $1$. The tree is

The answer is $1$.

After the second round, the sequence is $2, 1$. The tree is

The answer is $2+1=3$.

After the third round, the sequence is $2, 1, 3$. The tree is

The answer is $2+1+3=6$.

After the fourth round, the sequence is $2, 4, 1, 3$. The tree is

The answer is $1+4+1+2=8$.

After the fifth round, the sequence is $2, 4, 1, 5, 3$. The tree is

The answer is $1+3+1+5+1=11$.

第一轮后，序列为 $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$。