Rùa và Cầu thang hỏng

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nvatuan
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ngôi nhà của Rùa vừa rồi bị gặp động đất khiến cho cầu thang bị hư hại nặng nên Rùa muốn tu sửa lại chiếc cầu thang này. Cầu thang của Rùa có thể được cho là một mảng
\(A\) có \(N\) số, với mỗi số tượng trưng cho độ cao của nó. Rùa hiện đang ở bậc thang thứ \(1\) và muốn đến bậc thang thứ \(N\).

Ví dụ với A=[4,3,2,6]

Vì khả năng di chuyển có hạn mà Rùa chỉ di chuyển từ bậc thứ \(i\) đến bậc thứ \(i+1\) nếu như bậc \(i+1\) cao hơn bậc \(i\) tối đa 1 đơn vị. Cụ thể, Rùa có thể đi từ \(i\) đến \(i+1\) chỉ khi \(0 \leq A_{i+1} - A_i \leq 1\), với \(1 \leq i < N\).

Rùa có thể sửa cầu thang bằng cách chọn một bậc thang không phải bậc thứ \(1\) và thứ \(N\), sau đó nâng nó lên một số đơn vị bất kỳ tùy ý, và Rùa có thể thực hiện hành động sửa này nhiều lần.

Hỏi, có thể sửa cầu thang để Rùa đi từ bậc \(1\) đến bậc \(N\) hay không? In ra cầu thang đã sửa nếu có thể.

Input

  • Dòng đầu tiên chứa số nguyên \(N (2 ≤ N ≤ 2∗10^5)\)
  • Dòng thứ hai chứa \(N\) số nguyên, là phần tử mảng \(A\). \((1 ≤ A_i ≤ 10^6)\)

Dữ liệu đảm bảo \(A_1 < A_N\).

Output

Nếu không thể có cách nào, in ra impossible. Ngược lại, nếu có thể, hãy in ra \(N\) số là cầu thang sau khi đã sửa xong. Nếu có nhiều đáp án, hãy in ra một đáp án bất kỳ.

Example

Test 1

Input 
4
4 3 2 6
Output 
4 4 5 6
Note



Với kết quả là \([4,4,5,6]\) ta có hình minh họa như trên. Ngoài ra còn có kết quả khác đó là \([4,5,6,6]\).


Test 2

Input 
4
1 5 2 6
Output 
impossible

Bình luận