Поиск пирамиды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

У него под наблюдением находятся $$$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$$$-го изменения.

Пример

Входные данные
9
1 2 3 4 5 4 3 2 1
5
3 10
2 5
7 100000000
5 1
3 1
Выходные данные
6
6
4
5
5