주니어 가격 로봇

시간 제한1초메모리 제한1024 MB

요약

오늘 가격이 첫 번째로 주어지고 이전 날짜의 가격이 뒤따를 때, 오늘 가격 이하인 가장 최근 날짜가 며칠 전인지 출력한다.

난이도: 보통10점 중 5점
유형: 배열, 스택, 구현
정답자: 아직 제출이 없습니다

문제

최신 사업 아이디어인 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 2 \cdot 10^6$ 은 $i-1$ 일 전의 상품 가격이다. 오늘의 가격은 $p_1$ 이다.

출력

오늘의 BarGain 점수를 한 줄에 출력한다.

예제2

예제 1
입력
```
6
9 10 11 9 12 11
```
예상 출력
```
3
```
예제 2
입력
```
3
1 2 3
```
예상 출력
```
infinity
```