388. Stock Span

0

Medium

The stock span problem is a financial challenge that involves a series of N daily price quotes for a stock. The task is to calculate the stock's price span for each of the N days. Given an array of length N, where the i-th element represents the stock price on the i-th day, determine 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 defined as the maximum number of consecutive days before the (i+1)-th day, where 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, indicating 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