** Замечание: Время на тест для этой задачи 3 сек, в 1.5 раза больше чем по умолчанию.**
У Фермера Джона есть \(N\) (\(2 \leq N \leq 2 \cdot 10^5\)) коров, пронумерованных
от \(1\) до \(N\). На ферме должны состоятся выборы двух главных коров.
Изначально известно, что корова \(i\) проголосует за корову \(a_i\) (\(1 \leq a_i \leq N\)).
Определите двух главных коров, если ФД так организует процесс выборов:
- Выбирает произвольное подмножество \(S\) коров, которое содержит как минимум одну корову,
но не всех коров. ФД выбирает первой главной коровой корову \(x\), за которую проголосует
большинство коров из \(S\).
- ФД выбирает второй главной корову \(y\), за которую проголосует большинство из коров,
не вошедших в \(S\).
- Для фиксированного множества \(S\) ФД называет различием
между главными коровами \(|x - y|\). Поскольку ФД не хочет иметь главными коровами коров с
близкими номерами, он хочет выбрать \(S\) таким образом, чтобы максимизировать различие .
Если ФД не может выбрать две различных коровы главными, различие равно \(0\).
Однако, некоторые коровы изменяют своё мнение и ФД может проводить выборы несколько раз.
Поэтому он просит Вас ответить на \(Q\) (\(1 \leq Q \leq 10^5\)) вопросов.
В каждом запросе, одна корова меняет свой голос. Для каждого запроса нужно вновь получить ответ.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(Q\).
Следующая строка содержит \(a_1, a_2, \ldots, a_N\).
Последующие \(Q\) строк содержат два целых числа \(i\) и \(x\), представляющих
обновление \(a_i = x\) (\(1 \leq i, x \leq N\)).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(Q\) строк, \(i\)-ая из которых - максимальное различие
после первых \(i\) запросов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 2 3 4 5
3 4
1 2
5 2
|
4
3
2
|