Bài toán dọn rác

Trên trục số nguyên có một tập hợp các đống rác, đống thứ $i$ nằm tại tọa độ $p_i$. Tất cả các tọa độ đều đôi một khác nhau.

Một thao tác dồn toàn bộ được định nghĩa như sau: ta cần gom tất cả các đống về không quá hai tọa độ khác nhau. Để làm điều đó, ta thực hiện một số (có thể bằng $0$) bước. Mỗi bước, ta chọn một tọa độ $x$ và chuyển toàn bộ các đống đang ở tọa độ $x$ sang $x+1$ hoặc sang $x-1$ (không thể chỉ chuyển một phần).

Có $q$ truy vấn, mỗi truy vấn thuộc một trong hai loại:

• 0 x — xóa đống rác ở tọa độ $x$ (đảm bảo đang có đống tại $x$).
• 1 x — thêm một đống rác mới ở tọa độ $x$ (đảm bảo chưa có đống tại $x$).

Tại mọi thời điểm tập hợp có thể rỗng. Lưu ý rằng thao tác dồn toàn bộ chỉ dùng để tính toán — nó không thực sự được thực hiện và không làm thay đổi tập hợp các đống.

Hãy in ra số bước ít nhất cần dùng để dồn toàn bộ trước khi xử lý truy vấn đầu tiên, và sau mỗi truy vấn được áp dụng theo thứ tự.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$ ($1\le n,q\le {10}^5$).
• Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau $p_1,p_2,\dots ,p_n$ ($1\le p_i\le {10}^9$).
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $t_i$ và $x_i$ ($0\le t_i\le 1$, $1\le x_i\le {10}^9$) mô tả truy vấn.

Dữ liệu ra

In ra $q+1$ số: số bước tối thiểu trước truy vấn đầu tiên và sau mỗi truy vấn.

Ràng buộc

• $1\le n,q\le {10}^5$
• $1\le p_i,x_i\le {10}^9$

Ví dụ