Ngày gần nhất

Xem PDF

Nộp bài


Điểm: 15 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Thành phố Bytecity sẽ tổ chức một kỳ lễ hội kéo dài \(N\) ngày. Trong \(N\) ngày lễ đó, các ngày \(A_1\), \(A_2\), \(A_3\),..., \(A_M\) \((1\le A_1 < A_2 < A_3 < ... < A_M)\) sẽ có màn bắn pháo hoa. Dữ liệu đảm bảo \(A_M=N\), tức là luôn diễn ra sự kiện bắn pháo hoa trong ngày lễ cuối cùng. Với mỗi \(i=1,2,3,...,N\), bạn hãy trả lời câu hỏi: nếu một người gia nhập lễ hội từ ngày \(i\) thì họ phải chờ bao nhiêu ngày nữa mới được ngắm pháo hoa lần đầu?

Input
  • Dòng đầu chứa hai số nguyên dương \(N\) và \(M\) \(\left(1\le M\le N\le 2\times 10^5\right)\).
  • Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1\), \(A_2\), \(A_3\),..., \(A_M\) \((1\le A_1 < A_2 < A_3 < ... < A_M = N)\).
Output
  • In ra \(N\) dòng với dòng thứ \(i\) chứa một số nguyên là số lượng ngày mà một người cần chờ tính từ ngày thứ \(i\) để được xem pháo hoa lần đầu.
Ví dụ
Sample input 01
3 2
2 3
Sample output 01
1
0
0
Giải thích

Buổi bắn pháo hoa đầu tiên sẽ diễn ra từ ngày \(2\) nên tính từ ngày \(1\) thì ta phải chờ \(1\) ngày. Ngày \(2\) và ngày \(3\) đều diễn ra màn bắn pháo hoa nên những người gia nhập từ hai ngày này sẽ không phải chờ thêm ngày nào.

Sample input 02
8 5
1 3 4 7 8
Sample output 02
0
1
0
0
2
1
0
0