J. Shuttekka Panorama
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During Kantipa's vacation, from the room she is staying in, Kantipa can see $$$N$$$ mountains that are arranged in a single row. She numbers the mountains from $$$1$$$ to $$$N$$$ from left to right. Then, she constructs a permutation $$$A$$$ that's a permutation of $$$[1, 2, \ldots, N]$$$ which means mountain $$$i$$$ has the $$$A_i$$$-th lowest height out of the $$$N$$$ mountains.

Kantipa wants to take several panoramic photos of these mountains. To take a panoramic photo, she chooses two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$) and then takes a photo of all mountains from index $$$L$$$ to $$$R$$$. In the photo, Kantipa renumerates the mountains from $$$1$$$ to $$$R-L+1$$$ from left to right.

Kantipa thinks that the most important aspect of a panoramic photo is the position of the highest mountain in the photo. Therefore, she asks you, for each integer $$$k$$$ from $$$1$$$ to $$$N$$$, find the number of different ways to choose $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$) such that the tallest mountain in the photo is in the $$$k$$$-th position from the left (according to the new numbering in the photo).

Input

The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 200\,000$$$) — the number of mountains.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ — the height of each mountain. $$$A$$$ is a permutation of $$$[1, 2, \ldots, N]$$$.

Output

A single line containing $$$N$$$ integers, with the $$$k$$$-th integer representing the number of different ways to choose $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$) such that the tallest mountain in the photo is in the $$$k$$$-th position from the left (according to the new numbering in the photo).

Example
Input
4
1 2 4 3
Output
5 3 2 0
Note

Consider the following pairs of $$$(L, R)$$$:

  • The pairs $$$(1, 1)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$, $$$(4, 4)$$$ each has the tallest mountain at the $$$1$$$-st position.
  • The pairs $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$ each has the tallest mountain at the $$$2$$$-nd position.
  • The pairs $$$(1, 3)$$$, $$$(1, 4)$$$ each has the tallest mountain at the $$$3$$$-rd position.