Đèn Giao Thông

Có một con đường dài $x$ (từ vị trí $0$ đến $x$), ban đầu không có đèn giao thông nào. Các đèn được lắp thêm từng cái một. Sau mỗi lần lắp, hãy tính đoạn đường dài nhất không có đèn giao thông nào.

Dữ liệu vào

• Dòng 1: hai số nguyên $x$ và $n$
• Dòng 2: $n$ số nguyên $p_1,p_2,\dots ,p_n$ — vị trí các đèn được lắp theo thứ tự

Dữ liệu ra

In ra $n$ số nguyên trên một dòng — đoạn dài nhất sau mỗi lần lắp đèn.

Ràng buộc

• $1\le x\le {10}^9$
• $1\le n\le 2\times {10}^5$
• $0<p_i<x$, các vị trí đôi một khác nhau

Ví dụ