L. WA Sorting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On December 4th, ICPC2021 Nanjing was held. During the contest, Walk_alone (abbr. WA) did nothing but be stuck by Problem D, which was an easy data structure problem with a background of an adapted bubble sort. So he has being scolded by his teammates for a long time for losing a gold medal.

Today, his teammates gave him another adjusted sorting algorithm to help him overcome his psychological shadow. But his dread and fear stops him from even thinking about this problem. Help him solve the problem below to avoid being scolded by his teammates again!

Its pseudo-code is shown below.

Obviously not every sequence can be sorted by this algorithm, but it does not matter, and here comes the question:

Given a permutation $$$A=\{a_1,a_2,\cdots, a_n\}$$$. Let $$$A_k=\{a_1,a_2,\cdots, a_k\}$$$. Your task is to count the total number of times $$$m$$$ is assigned if we call $$${\rm SORT}(A_k)$$$ for every $$$k \ (1 \le k \le n)$$$.

Input

The first line contains an integer $$$n\ (1\le n\le 10^6)$$$ indicating the length of the sequence.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots, a_n\ (1\le a_i\le n)$$$ indicating the given permutation.

Output

Output one line containing $$$n$$$ integers $$$s_1,s_2,\cdots, s_n$$$ separated by a space, where $$$s_i$$$ indicates the total number of times $$$m$$$ is assigned if we call $$${\rm SORT}(A_i)$$$.

Examples
Input
6
5 4 2 6 3 1
Output
1 4 8 11 13 19
Input
6
4 5 2 3 6 1
Output
1 3 6 8 13 17