사탕 세일

캐시가 좋아하는 사탕 브랜드가 앞으로 n일 동안 하루에 한 가지씩 새로운 맛 n가지를 출시한다. i일째에 출시되는 맛 i의 한 봉지 가격은 출시 당일에 $w_i$ 달러이고, 출시한 다음 날부터는 하루가 지날 때마다 1달러씩 오른다. 즉 $j \ge i$인 날 j에 i일째 출시된 맛 한 봉지의 가격은

$w_i + (j - i)$

달러이다.

캐시는 앞으로 n일 동안 매일 사탕을 정확히 한 봉지씩 사고, 같은 돈으로 사탕을 최대한 많이 얻고 싶어 한다. 각 날짜마다 그날 살 수 있는 가장 싼 한 봉지의 가격을 구하라. 모든 맛은 재고가 무제한이고, 출시 당일과 그 뒤의 모든 날에 살 수 있다.

입력은 두 줄이다. 첫째 줄에 맛의 가짓수 n ($1 \le n \le 200\,000$)이 주어진다. 둘째 줄에 n개의 정수 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 100\,000$)이 주어진다. $w_i$는 i번째 맛의 출시 당일 가격이고 단위는 달러이다.

n개의 정수를 공백 하나로 구분해 한 줄에 출력한다. i번째 수는 i일째에 캐시가 살 수 있는 가장 싼 한 봉지의 가격이다.