781. Stock Span

0

Medium

The stock span problem involves analyzing a series of N daily price quotes for a stock to determine the span of the stock's price for each day. Given an array of length N, where the i-th element represents the price of the stock on the i-th day, find the span of the stock's price on the i-th day for every 1 <= i <= N. The span of the stock's price on a given day, i, is the maximum number of consecutive days before the (i+1)-th day for which the stock's price on those days is less than or equal to the price on the i-th day.

Input Format

The first line contains an integer N, denoting the size of the array.
The next line contains N space-separated integers, representing the elements of the array.

Output Format

Display the array containing the stock span values.

Example

Input

5
30
35
40
38
35

Output

1 2 3 1 1 END

Constraints

1 <= N <= 10^6

Loading...

View Submissions

Console