시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 373 182 71 51.449%

문제

정수 N개로 이루어진 배열 A가 주어진다. 상근이는 수열의 수 하나를 골라서 값을 1 감소시킬 수 있다. 단, 숫자는 1보다 작아질 수 없다.

상근이는 위의 감소시키는 연산을 최대 T번 하려고 한다. 이 때, 인접한 숫자의 차이의 최대값을 최소로 하는 프로그램을 출력하시오.

입력

첫째 줄에 N과 T가 주어진다.(2 ≤ N ≤ 100 000, 1 ≤ T ≤ 109)

둘째 줄에는 배열에 들어있는 수가 주어진다. (109보다 작은 자연수)

출력

첫째 줄에 인접합 숫자의 차이의 최대값을 가장 작게한 배열 A의 내용을 공백으로 구분하여 출력한다. 최대 T번 감소시켜야 한다.

예제 입력

5 5
4 2 3 7 6

예제 출력

3 2 3 4 5

힌트

각각의 테스트 케이스에 대해서, 점수는 (100*(S+1)/(D+1))/(데이터 개수) 점이다. 이 때, D는 출력한 수열에서 인접한 숫자의 차이의 최대값, S는 정답이다. 즉, 출력한 수열이 정답인 경우 10점을 얻게 된다. 하지만, 출력한 수열이 총 T번 감소시켜서 만들 수 없는 경우에는 그 테스트 케이스에 대해서 0점을 얻게 된다.

예를 들어, 위의 예제 출력을 "1 2 3 5 6"으로 하면 10*(2/3)=6.66점을 받게 된다. 정답은 1인데, 출력한 수열에서의 답은 2이기 때문이다.