허수아비

수직선의 위치 $0$에서 오른쪽 방향으로 힘 $P$를 가진 화살이 발사된다. 각 정수 위치 $i\ (1 \le i \le 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 \le i \le N$인 모든 $i$에 대하여 $f(i)$의 값을 구하는 프로그램을 작성하라.

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

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

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

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

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