Với bất kỳ dãy số nào, nếu ta có thể làm cho dãy đó trở thành dãy rỗng sau một số hữu hạn các thao tác xóa, ta gọi dãy đó là có thể xóa sạch. Một thao tác xóa được định nghĩa như sau:

• Gọi $k$ là độ dài hiện tại của dãy, xóa tất cả các phần tử trong dãy có giá trị bằng $k$.

Cho một dãy số $a$ có độ dài $n$ và $m$ thao tác sửa đổi. Sau mỗi lần sửa đổi thứ $i$, bạn cần trả lời câu hỏi: Với dãy $a$ sau $i$ lần sửa đổi, cần phải sửa đổi tối thiểu bao nhiêu phần tử nữa để dãy đó có thể xóa sạch?

Mỗi thao tác sửa đổi có thể là sửa đổi một phần tử đơn lẻ, cộng tất cả các phần tử trong dãy với một giá trị, hoặc trừ tất cả các phần tử trong dãy với một giá trị.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $n, m$, lần lượt là độ dài của dãy và số lần sửa đổi.

Dòng thứ hai chứa $n$ số nguyên dương, biểu thị dãy $a$, trong đó số thứ $i$ là $a_i$.

$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p, x$, biểu thị một thao tác sửa đổi.

Khi $1\le p \le n$, thao tác này là sửa đổi phần tử đơn lẻ, thay đổi phần tử thứ $p$ của dãy $a_p$ thành $x$.

Khi $p=0$, thao tác này là cộng toàn bộ dãy với $x$.

Dữ liệu ra

Xuất ra $m$ dòng, mỗi dòng một số nguyên, dòng thứ $i$ là câu trả lời sau $i$ lần sửa đổi.

Ví dụ

Dữ liệu vào 1

3 9
1 2 3
1 1
0 1
0 1
0 1
2 2
3 2
0 -1
0 -1
0 -1

Dữ liệu ra 1

0
1
2
3
2
1
1
2
2

Ghi chú

Sau lần sửa đổi thứ nhất, dãy là $(1, 2, 3)$, không cần sửa đổi gì thêm để xóa sạch.

Sau lần sửa đổi thứ tư, dãy là $(4, 5, 6)$, cần phải sửa đổi cả ba số mới có thể xóa sạch.

Sau lần sửa đổi thứ sáu, dãy là $(4, 2, 2)$, sửa phần tử đầu tiên thành $3$ là có thể xóa sạch.

Sau lần sửa đổi thứ chín, dãy là $(1, -1, -1)$, có thể sửa phần tử thứ hai thành $2$ và phần tử thứ ba thành $3$ để xóa sạch.

Nhiệm vụ con

Với $100\%$ dữ liệu:

• $1\le n,m \le 1.5 \times 10^5$
• $1\le a_i \le n$
• $0\le p\le n$
  • Khi $p>0$, $1\le x \le n$.
  • Khi $p=0$, $x=-1$ hoặc $1$.