Stock Span

Difficulty: 1400 3500 ms 128 MB

stack

The span of day i counts the consecutive days ending at i (including i) with price ≤ the price on day i. Print every day's span.

Input: the first line has N; the second line has the N prices.

Output: N integers: the span of each day.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ p_i ≤ 10⁹

Sample Tests

7
100 80 60 70 60 75 85

1 1 1 2 1 4 6

1
5

1

Read the Editorial