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