Counting in pyramids You should write a program or function which receives a list of distinct integers as input and outputs or returns the number of occurrences of the input numbers in the following upside-down number pyramid.

Starting from the original list in every step we create a new one with the maximal values of every pair of adjacent numbers (e.g. 5 1 2 6 becomes 5 2 6). We stop when there is only one number in the list.

The full pyramid for 5 1 2 6 is

5 1 2 6
 5 2 6 
  5 6  
   6   


The resulting number of occurrences are 3 1 2 4 (for 5 1 2 6 respectively).

Input


A list of one or more integers with no repetition. (e.g. 1 5 1 6 is invalid.)


Output


A list of positive integers. The ith element of the list is the number of occurrences of the ith input number in the pyramid.


Examples

Input => Output

-5 =&gt; 1

8 4 =&gt; 2 1

5 9 7 =&gt; 1 4 1

1 2 3 9 8 6 7 =&gt; 1 2 3 16 3 1 2

6 4 2 1 3 5 =&gt; 6 4 2 1 3 5

5 2 9 1 6 0 =&gt; 2 1 12 1 4 1

120 5 -60 9 12 1 3 0 1200 =&gt; 8 2 1 3 16 1 4 1 9

68 61 92 58 19 84 75 71 46 69 25 56 78 10 89 =&gt; 2 1 39 2 1 27 6 5 1 6 1 2 14 1 12


This is code-golf so the shortest entry wins.

Bonus puzzle: can you solve the problem in O(n*log n) time?
Python, 81

def f(L):
 if L:i=L.index(max(L));L=f(L[:i])+[~i*(i-len(L))]+f(L[i+1:])
 return L


A divide-and-conquer solution. The maximum element M seeps all the way down the pyramid, splitting it into a rectangle of M's and two subpyramids.

* * * M * *
 * * M M *
  * M M M
   M M M
    M M
     M


So, the overall result is the output for the left sublist, followed by the area of the rectangle, followed by the output for the right sublist.

The input variable L is reused to stored the result so that the empty list is mapped to the empty list.

The constructs in solution are wordy in Python. Maybe some language with pattern-matching can implement the following pseudocode?

def f(L):
 [] -&gt; []
 A+[max(L)]+B -&gt; f(A)+[(len(A)+1)*(len(B)+1)]+f(B)