Bài toán: Đèn giao thông

Đề bài

Có một con đường dài ~ x ~ với các vị trí được đánh số từ ~ 0, 1, \ldots, x ~. Ban đầu không có đèn giao thông. Sau đó, ~ n ~ vị trí đèn giao thông được thêm vào từng cái một.

Nhiệm vụ của bạn là tính độ dài đoạn đường dài nhất không có đèn giao thông sau mỗi lần thêm đèn giao thông.

Input

• Dòng đầu tiên chứa hai số nguyên ~ x ~ (độ dài đường) và ~ n ~ (số lượng đèn giao thông).
• Dòng thứ hai chứa ~ n ~ số nguyên ~ p_1, p_2, \ldots, p_n ~: các vị trí đặt đèn giao thông (các vị trí này là duy nhất).

Output

• In ra ~ n ~ dòng, mỗi dòng là độ dài đoạn đường dài nhất không có đèn giao thông sau mỗi lần thêm đèn giao thông.

Ví dụ

Input:

8 3
3 6 2

Output:

5 3 3

Giải thích:

• Sau khi thêm đèn ở ~ 3 ~: đoạn dài nhất là ~ 5 ~ (~ [0, 3] ~ và ~ [3, 8] ~).
• Sau khi thêm đèn ở ~ 6 ~: đoạn dài nhất là ~ 3 ~ (~ [0, 3], [3, 6], [6, 8] ~).
• Sau khi thêm đèn ở ~ 2 ~: đoạn dài nhất là ~ 3 ~ (~ [0, 2], [2, 3], [3, 6], [6, 8] ~).

Ràng buộc

• ~ 1 \leq x \leq 10^9 ~
• ~ 1 \leq n \leq 2 \cdot 10^5 ~
• ~ 0 < p_i < x ~