스피키 정렬

스피키 네르지 마세요!

— 스핔이, 「트릭컬 리바이브」

$N$명의 스피키가 한 줄로 서 있다. $i$번째 스피키의 키는 $A_i$이다. 이때, 아래의 네르기 연산을 $0$회 이상 원하는 만큼 할 수 있다.

• 정수 $i\,(1\leq i \leq N)$를 선택하여 $A_i$의 값을 $1$ 이상 $A_i$ 이하의 원하는 정수로 바꾼다.

네르기 연산을 최소 횟수로 사용하여 $A$를 단조증가하는 수열로 만들어보자.

첫 번째 줄에 정수 $N$이 주어진다. $(2 \leq N \leq 300\,000)$

두 번째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백을 사이에 두고 주어진다. $(1 \leq A_i \leq {10}^9)$

첫 번째 줄에 $A$를 단조증가하는 수열로 만들기 위해 필요한 네르기 연산의 최소 횟수를 출력한다.

두 번째 줄에 최소한의 네르기 연산들을 적용한 후의 $A_1, A_2, \dots, A_N$을 공백을 사이에 두고 출력한다.

답으로 가능한 수열 $A$가 여러 가지일 경우, 그 중 아무 것이나 출력한다.