건초 더미 최소화

시간 제한4초메모리 제한512 MB

요약

인접한 두 스택의 높이 차이가 K 이하이면 서로 바꿀 수 있을 때, 도달할 수 있는 높이 수열 중 사전순으로 가장 작은 것을 구합니다.

난이도: 보통10점 중 7점
유형: 위상 정렬, 세그먼트 트리, 힙
정답자: 아직 제출이 없습니다

문제

Bessie는 심심해서 또 Farmer John의 헛간에서 말썽을 피우고 있다. FJ에게는 $N$ ( $1\leq N \leq 10^5$ )개의 건초 더미가 있다. 각 $i\in [1,N]$ 에 대해 $i$ 번째 더미에는 $h_i$ ( $1\le h_i\le 10^9$ )개의 건초가 쌓여 있다. Bessie는 건초가 떨어지는 것을 원하지 않으므로, 다음 연산만 수행할 수 있다.

인접한 두 더미의 높이 차이가 $K$ ( $1\le K\le 10^9$ ) 이하이면, 두 더미를 교환할 수 있다.

이 연산들을 몇 번 수행한 뒤 얻을 수 있는 높이 수열 중에서 사전순으로 가장 작은 것은 무엇인가?

입력

첫 줄에 $N$ 과 $K$ 가 주어진다. $i+1$ 번째 줄에는 $i$ 번째 건초 더미의 높이가 주어진다.

출력

$N$ 줄을 출력한다. $i$ 번째 줄에는 해답에서 $i$ 번째 건초 더미의 높이를 출력한다.

힌트

Bessie는 다음과 같이 더미를 교환할 수 있다.

   7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3

예제1

예제 1
입력
```
5 3
7
7
3
6
2
```
예상 출력
```
6
7
7
2
3
```