Stock Span

easy

1. Implement the functions of class StockSpanner.
  2. next() collects daily price quotes for the stock, and returns the span of that stock's price for the current day.
  3. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.
  
  Example
  If the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], 
  then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Input Format

First line contains the total no. of days 'N'. Second line contains the value of stock at the corresponding day

Output Format

An integer array containing the span at the corresponding day.

Constraints

Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
  There will be at most 10000 calls to StockSpanner.next per test case.

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

7
100 80 60 70 60 75 85

Output

Sliding Window Maximum