Пошук піраміди#11094
"Фуфелшмертц Пакість Інкорпорейтед" знову завдає шкоди! Тепер він щодня зсуває літосферні плити Землі. Перрі-качконіс отримав важливе завдання: щодня знаходити найпідозріліший рельєф на прямій і, звісно, повідомляти про нього в агентство.
Під його наглядом знаходяться ділянок, розташованих на одній прямій. Кожна ділянка характеризується числом h_i, що є висотою цієї ділянки над рівнем моря. Відрізок називається підозрілим, якщо на ньому існує така ділянка, що висоти ділянок лівіше неї строго зростають, а правіше строго спадають. Через витівки Фуфелшмерца висоти ділянок постійно змінюються.
Допоможіть Перрі визначити довжину найдовшого підозрілого відрізка ділянок після кожної зміни. Гарантується, що в будь-який момент часу немає двох сусідніх ділянок з однаковою висотою.
У першому рядку дано одне число (1 \le n \le 10^5) - кількість ділянок. У другому рядку дано чисел - висоти ділянок (|h_i| \le 10^{18}).
У третьому рядку дано число (1 \le m \le 10^5) - кількість змін. У наступних рядках дано по два цілих числа і (1 \le x \le n, |y| \le 10^{18}) - індекс ділянки, висота якої змінилася, і нове значення висоти для цієї ділянки, відповідно.
Виведіть чисел, де -те число дорівнює довжині найбільшого підозрілого відрізка після -ї зміни.
Приклад 1