You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
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!

## Input Format
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.

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

## Examples
```input
5
2 4 1 5 3
```
```output
1
3
6
8
11
```
-----
```input
6
1 2 4 5 6 3
```
```output
1
3
6
8
12
17
```

## Note
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$$$.

Now solve the problem and return the code.