B'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: 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 <= n <= 150000 ). The second line contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= 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 rou'...