E. Cartesian Tree
data structures
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: If the sequence is empty, return an empty tree; Let the position of the maximum element be \(x\); 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); Build cartesian tree for each part; 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; 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!
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.
Print \(n\) lines, \(i\)-th line should contain a single integer — the answer to the \(i\)-th question.
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\).