Hide
Problem E
Elder price robot
The idea behind your latest business adventure, BarGain
Overview (BGO), is to collect the history of prices for a
certain item that is available for sale on the web. The
BarGain score of a particular day is defined as the
number of days since the price was lower or equal to today’s
price. The worst BarGain score is thus $1$, and if the price is strictly
better than all previous prices ever recorded, then it is
infinity. You want to report the
BarGain score to your customers to help them identify a good
buy.
Input
The first line of input contains a single integer $2 \leq n \leq 400\, 000$, the number of days for which you have collected price data for the item. On the second line of input follows $n$ space-separated integers $p_1, p_2, \ldots , p_{n}$, where $0 \leq p_ i \leq 10^6$ is the price of the item $i-1$ days ago. Today’s price is $p_1$.
Output
Output $n$ rows, one for each day you have collected price data for the item. On the $i^{\text {th}}$ such line, output the BarGain score for the day that was $i-1$ days ago.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 9 10 11 9 12 11 |
3 2 1 infinity 1 infinity |
