장로 가격 로봇

최신 사업 아이디어인 BarGain Overview(BGO)는 웹에서 판매되는 특정 상품의 가격 이력을 수집하는 것이다. 특정 날짜의 BarGain 점수는 그날의 가격보다 낮거나 같은 가격이었던 날로부터 며칠이 지났는지로 정의된다. 따라서 최악의 BarGain 점수는 $1$이고, 그날의 가격이 이전에 기록된 모든 가격보다 엄격하게 좋으면 infinity이다. 고객이 좋은 구매 시점을 찾을 수 있도록 BarGain 점수를 알려 주려 한다.

첫째 줄에 가격 데이터를 수집한 날 수를 나타내는 정수 $2 \leq n \leq 400\,000$이 주어진다. 둘째 줄에 $n$개의 정수 $p_1, p_2, \ldots, p_{n}$가 공백으로 구분되어 주어진다. $0 \leq p_i \leq 10^6$은 $i-1$일 전의 상품 가격이다. 오늘의 가격은 $p_1$이다.

가격 데이터를 수집한 각 날에 대해 한 줄씩, 총 $n$개의 줄을 출력한다. $i$번째 줄에는 $i-1$일 전의 날에 대한 BarGain 점수를 출력한다.