Lưu ý: Giới hạn thời gian của bài này là 3 giây, bằng 1,5 lần giới hạn mặc định.

Farmer John có \(N\) (\(2\leq N\leq 2\cdot 10^5\)) con bò được đánh số từ \(1\) đến \(N\). Một cuộc bầu cử đang được tổ chức tại trang trại của FJ để chọn ra hai bò lãnh đạo mới. Ban đầu, biết rằng bò \(i\) sẽ bỏ phiếu cho bò \(a_i\) (\(1\leq a_i\leq N\)).

Để chọn ra hai bò lãnh đạo, FJ tiến hành cuộc bầu cử theo quy trình sau:

• Chọn một tập con tùy ý \(S\) gồm ít nhất một con bò nhưng không gồm tất cả các con bò. FJ có thể chọn bò \(x\) làm bò lãnh đạo thứ nhất nếu số phiếu dành cho nó xuất hiện nhiều nhất trong tất cả các phiếu của những con bò thuộc \(S\).
• FJ có thể chọn bò \(y\) làm bò lãnh đạo thứ hai nếu số phiếu dành cho nó xuất hiện nhiều nhất trong tất cả các phiếu của những con bò không thuộc \(S\).
• Với một tập con \(S\) cố định, FJ định nghĩa độ đa dạng giữa hai bò lãnh đạo là \(|x-y|\). Vì FJ không thích các lãnh đạo có số hiệu gần nhau, ông muốn chọn \(S\) sao cho độ đa dạng lớn nhất. Lưu ý rằng nếu FJ không thể chọn hai bò lãnh đạo khác nhau thì độ đa dạng bằng \(0\).

Tuy nhiên, một số con bò liên tục thay đổi ý định, và FJ có thể phải tổ chức lại cuộc bầu cử nhiều lần! Vì vậy, ông hỏi bạn \(Q\) (\(1\leq Q\leq 10^5\)) truy vấn. Trong mỗi truy vấn, một con bò thay đổi lá phiếu của mình. Sau mỗi truy vấn, ông hỏi độ đa dạng lớn nhất có thể có giữa hai bò lãnh đạo mới.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa \(a_1,a_2,\ldots,a_N\).

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(x\), biểu thị cập nhật \(a_i=x\) (\(1\leq i,x\leq N\)).

Dữ liệu ra

In ra \(Q\) dòng; dòng thứ \(i\) là độ đa dạng lớn nhất có thể sau \(i\) truy vấn đầu tiên.

Ví dụ

5 3
1 2 3 4 5
3 4
1 2
5 2

4
3
2

8 5
8 1 4 2 5 4 2 3
7 4
8 4
4 1
5 8
8 4

4
4
4
7
7

Phân nhóm

• Dữ liệu 3–4: \(N,Q\leq 100\).
• Dữ liệu 5–7: \(N,Q\leq 3000\).
• Dữ liệu 8–15: Không có ràng buộc bổ sung.

Đề bài: Chongtian Ma và Haokai Ma.

Nguồn

USACO 2025 US Open Contest, Gold — Election Queries: https://usaco.org/index.php?page=viewproblem2&cpid=1522