수직선의 위치 0에서 오른쪽 방향으로 힘 P 를 가진 화살이 발사된다.

각 정수 위치 i(1≤i≤N)에는 방어력 A_i 를 가진 허수아비를 최대 하나 설치할 수 있다.

화살이 허수아비에 부딪치면, 화살의 힘이 방어력보다 작거나 같을 경우 화살은 즉시 멈춘다.

반대로 화살의 힘이 방어력보다 크면, 화살의 힘은 현재 화살의 힘에서 Ai 만큼 줄어든 채 계속 진행한다.

정수 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)의 값과 설치한 허수아비의 위치는 다음과 같다.

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

허수아비 timer 2s memory 1024MB

허수아비 2s 1024MB