허수아비

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

$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$