#520. BITMUSIC – Nghe nhạc

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nam có một bộ sưu tập n đĩa nhạc. Cậu đánh số hiệu các đĩa theo thứ tự từ 1 đến n . Ban đầu các đĩa được xếp chồng lên nhau theo đúng thứ tự từ 1 đến n từ trên xuống dưới (đĩa có số hiệu là n ở dưới cùng). Khi muốn nghe một đĩa nhạc nào đó, Nam sẽ rút đĩa đó ra, nghe xong thì để đĩa lại vào vị trí trên cùng. Giả sử Nam có m lần rút đĩa nghe nhạc, hãy cho biết tại mỗi lần rút một đĩa, có bao nhiêu đĩa khác đang ở phía trên đĩa đó.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương n, m là số đĩa nhạc và số lần rút đĩa;
  • Dòng thứ hai chứa m số nguyên a_1, a_2, …, a_m là số hiệu các đĩa được rút ra mỗi lần.

Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

  • Ghi trên một dòng m số nguyên không âm thể hiện số lượng đĩa ở phía trên đĩa được rút trong m lần rút đĩa. Hai số liên tiếp ghi cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:
5 2
5 3
Dữ liệu ra:
4 3
Giải thích:
  • Ban đầu thứ tự các đĩa là 1 2 3 4 5 . Khi rút đĩa nhạc số 5 , có 4 đĩa khác đang ở trên nó (1, 2, 3, 4) . Khi rút đĩa nhạc số 3 , có 3 đĩa khác đang ở trên nó (5, 1, 2) .

Giới hạn:

  • 1 ≤ n, m ≤ 10^5; 1 ≤ a_i ≤ n .