🔁 Đề bài

JSOI có N ngọn núi được xếp liên tiếp theo một hàng thẳng. Chiều cao của ngọn núi thứ i là ~ h_i ~.

Mỗi ngọn núi có thể được gắn một chiếc đèn, và chiếc đèn này sẽ có một độ cao ~ p ~. Đèn ở ngọn núi thứ i có thể chiếu sáng đến các ngọn núi khác nếu thỏa mãn điều kiện sau: ~ h_j \le h_i + p - \sqrt{|i - j|} ~ Với mỗi ngọn núi i, bạn cần tìm độ cao nhỏ nhất của chiếc đèn sao cho chiếc đèn này có thể chiếu sáng tất cả các ngọn núi khác.

Input

• Dòng đầu tiên chứa một số nguyên N (1 ≤ N ≤ 10^5), là số lượng ngọn núi.
• Dòng thứ hai chứa N số nguyên, mỗi số là chiều cao của các ngọn núi ~ h_1, h_2, \dots, h_N ~ (1 ≤ h_i ≤ 10^9).

Output

• In ra N dòng, mỗi dòng là độ cao nhỏ nhất của chiếc đèn đặt tại ngọn núi thứ i, sao cho chiếc đèn này có thể chiếu sáng tất cả các ngọn núi khác.

Ví dụ

Ví dụ 1:

Input:

6
5 3 4 2 3 4

Output:

2
3
3
5
4
4

Giải thích:

• Ngọn núi đầu tiên có chiều cao 5. Để chiếu sáng tất cả các ngọn núi còn lại, chiếc đèn cần có chiều cao ít nhất là 2.
• Ngọn núi thứ 2 có chiều cao 3. Để chiếu sáng tất cả các ngọn núi còn lại, chiếc đèn cần có chiều cao ít nhất là 3.
• Tương tự cho các ngọn núi còn lại.