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
i
th element of the list is the number of occurrences of thei
th input number in the pyramid.
Examples
Input => Output
-5 => 1
8 4 => 2 1
5 9 7 => 1 4 1
1 2 3 9 8 6 7 => 1 2 3 16 3 1 2
6 4 2 1 3 5 => 6 4 2 1 3 5
5 2 9 1 6 0 => 2 1 12 1 4 1
120 5 -60 9 12 1 3 0 1200 => 8 2 1 3 16 1 4 1 9
68 61 92 58 19 84 75 71 46 69 25 56 78 10 89 => 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?