60002 허수아비 Gold III

문제

수직선의 위치 $0$에서 오른쪽 방향으로 힘 $P$를 가진 화살이 발사된다. 각 정수 위치 $i$ ($1 ≤ i ≤ N$)에는 방어력 $A_i$를 가진 허수아비를 최대 하나 설치할 수 있다. 화살이 허수아비에 부딪치면, 화살의 힘이 방어력보다 작거나 같을 경우 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 화살의 힘은 현재 화살의 힘에서 $A_i$만큼 줄어든 채 계속 진행한다.

정수 $i$에 대하여 $f(i)$의 값을 “화살이 위치 $i$에서 멈추거나 위치 $i$보다 왼쪽에서 멈추도록 하기 위해 필요한 허수아비의 최소 개수” 라고 정의하자. 화살을 멈추게 할 수 있는 방법이 없을 때의 값은 $−1$이다.

예를 들어서 $N = 5$, $P = 10$이고 $A_1 = 3$, $A_2 = 6$, $A_3 = 1$, $A_4 = 1$, $A_5 = 10$이라고 하자. 모든 $f(i)$의 값과 설치한 허수아비의 위치는 다음과 같다.

$i$	$f(i)$의 값	설치한 허수아비의 위치
$i = 1$	$-1$	불가능
$i = 2$	$-1$	불가능
$i = 3$	$3$	$[1, 2, 3]$
$i = 4$	$3$	$[1, 2, 3]$ 혹은 $[1, 2, 4]$ 중 하나 선택 가능
$i = 5$	$1$	$[5]$

$1 ≤ i ≤ N$인 모든 $i$에 대하여 $f(i)$의 값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 정수 $N$과 화살의 힘 $P$가 공백을 사이에 두고 주어진다.

두 번째 줄에 $N$개의 정수 $A_1 , A_2 ,\cdots, A_N$이 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 $f(1), f(2), \cdots , f(N)$의 값을 공백을 사이에 두고 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ N ≤ 500\, 000$
• $1 ≤ P ≤ 10^9$
• $1 ≤ i ≤ N$인 모든 $i$에 대하여 $1 ≤ A_i ≤ 10^9$

서브태스크

번호	배점	제한
1	4	$N ≤ 8$
2	8	$N ≤ 5\, 000$
3	8	$1 ≤ i ≤ N$인 모든 $i$에 대하여 $A_i = 1$
4	20	$1 ≤ i ≤ N$인 모든 $i$에 대하여 $A_i = 2$ 또는 $A_i = 3$
5	40	$1 ≤ i ≤ N$인 모든 $i$에 대하여 $A_i ≤ 50$
6	40	$1 ≤ i < N$인 모든 $i$에 대하여 $A_i \le A_{i+1}$
7	30	추가 제약 조건 없음.

5 10
3 6 1 1 10

-1 -1 3 3 1

3 10
20 20 20

1 1 1

1 5
3

-1