Rút sách

Quân đẹp trai là một người rất thích đọc sách, nhưng khổ nỗi Quân nghèo nên số sách Quân sở hữu cũng khá là ít. Vì vậy nên Quân rất hay tới thư viện, nơi có hàng nghìn quyển sách để Quân thoải mái đọc. Có một điều đặc biệt là, mỗi ngày, Quân đều tới thư viện mượn \(N\) quyển sách. Các quyển sách được Quân đánh số từ \(1\) đến \(N\) (tất nhiên khi trả sách cho thư viện thì Quân sẽ xóa những số này đi, và tất nhiên Quân sẽ không làm hư hại tới quyển sách nào cả).

Lúc về nhà, Quân sẽ xếp chồng các quyển sách lên nhau theo đúng thứ tự từ \(1\) tới \(N\), nghĩa là quyển sách có số thứ tự \(1\) sẽ nằm ở trên cùng, tiếp đó quyển sách có số thứ tự \(2\), ... , quyển sách có số thứ tự \(N\) sẽ nằm ở dưới cùng của chồng sách. Tiếp đó, Quân sẽ đi mua trà sữa và bánh tráng nướng để vừa ăn vừa đọc.

Khi muốn đọc quyển sách nào, Quân sẽ rút quyển đó ra khỏi chồng sách. Sau khi đọc xong, Quân sẽ để quyển sách vừa đọc lên trên cùng của chồng sách. Giả sử Quân có \(M\) lần rút sách, hãy cho biết tại mỗi lần rút, có bao nhiêu quyển sách khác đang nằm phía trên quyển sách chuẩn bị rút.

Input

Dòng thứ nhất gồm hai số nguyên dương \(N, M (N, M <= 10^5)\) - số quyển sách và số lần rút sách

Dòng thứ hai gồm M số nguyên dương \(a_{1}, a_{2}, ..., a_{m} (1 <= a_{i} <= N)\) - số thứ tự của quyển sách ở lần rút thứ \(i\)

Output

Gồm \(M\) số nguyên, mỗi số cách nhau một dấu cách, thể hiện số lượng sách đang nằm phía trên quyển sách chuẩn bị rút.

Example

5 2
5 3

4 3 

5 4
2 3 4 5

1 2 3 4 

5 3
3 3 2

2 0 2 

Scoring

Có 50 phần trăm số test có \(N, M <= 10^3\).
50 phần trăm số test còn lại không có ràng buộc gì thêm.