Truy Vấn Bầu Cử

Farmer John tổ chức bầu cử với $N$ con bò. Mỗi con bò $i$ bỏ phiếu cho bò $a_i$. FJ chọn tập con $S$ (không rỗng, không phải toàn bộ) sao cho:

• $x$ = bò nhận nhiều phiếu nhất trong $S$ (trưởng nhóm 1)
• $y$ = bò nhận nhiều phiếu nhất ngoài $S$ (trưởng nhóm 2)

Độ đa dạng = $|x-y|$, hoặc $0$ nếu $x=y$.

Sau mỗi truy vấn cập nhật (thay đổi phiếu của một con bò), in độ đa dạng lớn nhất có thể.

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: Hai số nguyên $i$ và $x$ — đổi $a_i=x$.

Dữ liệu ra

• $Q$ dòng, mỗi dòng là độ đa dạng lớn nhất sau cập nhật.

Ràng buộc

• $2\le N\le 2\times {10}^5$
• $1\le Q\le {10}^5$
• Giới hạn thời gian: 3 giây

Ví dụ