E. The Perfect Gift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is almost Valentine's Day and Bob has found the perfect gift for Alice: a permutation of the integers $$$0, ..., n-1$$$! Bob knows that MEX is Alice's favorite function, and for this reason he wants to write for each index $$$i$$$, the sum of MEX over all subarrays of the permutation that contain index $$$i$$$. Unfortunately this is difficult for Bob to compute so he needs your help.

Formally, you are given a permutation $$$a_1, ..., a_n$$$ consisting of (distinct) integers $$$0, ..., n-1$$$. For each $$$1 \leq i \leq n$$$, determine the sum of $$$\text{MEX}(a[l, r])$$$ for each $$$1 \leq l \leq r \leq n$$$ where $$$a[l, r]$$$ represents the subarray $$$a_l, a_{l+1}, ... a_r$$$, and $$$\text{MEX}(b)$$$ outputs the smallest non-negative integer $$$k$$$ such that $$$k$$$ doesn't appear in $$$b$$$.

Input

The first line of input will contain a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — denoting the size of the permutation Bob found. The next line will contain $$$n$$$ distinct integers $$$a_1, ..., a_n$$$ ($$$0 \leq a_i \leq n-1$$$) — describing the permutation itself.

Output

The output will consist of $$$n$$$ lines. On the $$$i$$$th line, output the sum of MEX over all subarrays of $$$a$$$ containing index $$$i$$$.

Examples
Input
3
0 1 2
Output
6
5
3
Input
5
1 2 0 3 4
Output
12
15
18
13
7