Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Cartesian Tree

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIldar 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!

Input

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

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/20/2021 19:32:48 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|