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