Truy Vấn Bầu Cử

Trại của Farmer John có $N$ con bò được đánh số từ $1$ đến $N$. Trong cuộc bầu cử, con bò thứ $i$ bỏ phiếu cho con bò $a_i$.

Farmer John chọn một tập $S$ gồm các con bò, với $S$ khác rỗng và $S$ không chứa toàn bộ $N$ con bò. Hai nhóm bò sau đó bầu ra hai trưởng nhóm:

• $x$ là con bò nhận được nhiều phiếu nhất trong số các lá phiếu do những con bò thuộc $S$ bỏ ra.
• $y$ là con bò nhận được nhiều phiếu nhất trong số các lá phiếu do những con bò không thuộc $S$ bỏ ra.

Nếu có nhiều con bò cùng nhận được số phiếu nhiều nhất trong một nhóm thì nhóm đó được chọn bất kỳ con nào trong số chúng làm trưởng nhóm. Trưởng nhóm không nhất thiết phải thuộc nhóm đã bầu ra nó.

Độ đa dạng của một cách chọn là $|x-y|$.

Có $Q$ truy vấn cập nhật, truy vấn thứ $j$ đổi giá trị $a_{i_j}$ thành $x_j$. Các cập nhật có hiệu lực lâu dài (truy vấn sau tác động lên mảng đã được cập nhật bởi các truy vấn trước). Sau mỗi truy vấn, hãy in ra độ đa dạng lớn nhất mà Farmer John có thể đạt được, khi được tự do chọn tập $S$ và chọn hai trưởng nhóm.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $Q$.
• Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$.
• $Q$ dòng tiếp theo: Dòng thứ $j$ chứa hai số nguyên $i_j$ và $x_j$, nghĩa là gán $a_{i_j}=x_j$.

Dữ liệu ra

• $Q$ dòng, dòng thứ $j$ là độ đa dạng lớn nhất sau khi thực hiện truy vấn thứ $j$.

Ràng buộc

• $2\le N\le 2\times {10}^5$
• $1\le Q\le {10}^5$
• $1\le a_i\le N$
• $1\le i_j\le N$ và $1\le x_j\le N$

Ví dụ