최소 비용 증가 수열

길이가 $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\}$이다.