28650번 - Поиск пирамиды 다국어

<<Фуфелшмертц Пакость Инкорпорейтед>> опять пакостит! Теперь он ежедневно сдвигает литосферные плиты Земли. Перри-утконос получил важное задание: каждый день искать самый подозрительный рельеф на прямой и затем, разумеется, сообщать о нем в агентство.

У него под наблюдением находятся $n$ участков, расположенных на одной прямой. Каждый участок характеризуется одним числом $h_i$ --- высотой данного участка над уровнем моря. Отрезок называется подозрительным, если на нем существует такой участок, что высоты участков левее него строго возрастают, а правее --- строго убывают. При этом, из-за проделок Фуфелшмерца высоты участков постоянно меняются.

Помогите Перри определить длину самого длинного подозрительного отрезка участков после каждого изменения. Гарантируется, что в любой момент времени нет двух рядом стоящих участков с одинаковой высотой.

В первой строке дано одно число $n$ --- количество участков ($1 \le n \le 100\,000$). Во второй строке дано $n$ чисел --- высоты участков ($|h_i| \le 10^{18}$).

В третьей строке дано число $m$ --- количество изменений ($1 \le m \le 100\,000$). В следующих $m$ строках дано по два целых числа $x$ и $y$ --- индекс участка, высота которого изменилась, и новое значение высоты для этого участка, соответственно ($1 \le x \le n$, $|y| \le 10^{18}$).

Выведите $m$ чисел, $i$-е из которых равно длине наибольшего подозрительного отрезка после $i$-го изменения.