최소 비용 증가 수열

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

요약

|B_i - A_i|의 합이 최소가 되도록 수열 A를 순증가 정수 수열 B로 바꾸고, 그중 사전순으로 가장 작은 B를 출력한다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 그리디, 힙
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 인 정수 수열 $A_1, A_2, \dots, A_N$ 이 주어진다.

$B_1 < B_2 < \dots < B_N$ 을 만족하는 정수 수열 $B$ 가운데 $|B_1 - A_1| + |B_2 - A_2| + \dots + |B_N - A_N|$ 을 최소로 만드는 것을 찾아야 한다. $B$ 의 모든 원소는 32비트 부호 있는 정수 범위 안에 들어간다.

합을 최소로 만드는 $B$ 는 여러 개일 수 있다. 그중 사전순으로 가장 앞서는 것을 출력한다. 즉 $B_1$ 을 될 수 있는 대로 작게 잡고, 그 값을 고정한 뒤 $B_2$ 를 될 수 있는 대로 작게 잡는 식으로 정한다.

입력

첫째 줄에 $N$ 이 주어진다. ( $1 \le N \le 10^6$ )

둘째 줄에 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어진다. ( $0 \le A_i \le 2 \times 10^9$ )

출력

사전순으로 가장 앞서는 최적 수열 $B$ 를 $N$ 개의 줄에 한 원소씩 출력한다.

힌트

$A = \{9, 4, 8, 20, 14, 15, 18\}$ 일 때 합의 최솟값은 $13$ 이다. 이 값을 만드는 $B$ 는 하나가 아니어서 $B = \{6, 7, 8, 13, 14, 15, 18\}$ 의 합도 $13$ 이다. 사전순으로 가장 앞서는 것은 $B = \{3, 4, 8, 13, 14, 15, 18\}$ 이다.

예제3

예제 1
입력
```
7
9 4 8 20 14 15 18
```
예상 출력
```
3
4
8
13
14
15
18
```
예제 2
입력
```
1
0
```
예상 출력
```
0
```
예제 3
입력
```
5
1 2 3 4 5
```
예상 출력
```
1
2
3
4
5
```