Поиск пирамиды
Поиск пирамиды
"Фуфелшмертц Пакость Инкорпорейтед" опять пакостит! Теперь он ежедневно сдвигает литосферные плиты Земли. Перри-утконос получил важное задание: каждый день искать самый подозрительный рельеф на прямой и затем, разумеется, сообщать о нем в агентство.
У него под наблюдением находятся n участков, расположенных на одной прямой. Каждый участок характеризуется одним числом hi
- высотой данного участка над уровнем моря. Отрезок называется подозрительным, если на нем существует такой участок, что высоты участков левее него строго возрастают, а правее строго убывают. При этом, из-за проделок Фуфелшмерца высоты участков постоянно меняются.
Помогите Перри определить длину самого длинного подозрительного отрезка участков после каждого изменения. Гарантируется, что в любой момент времени нет двух рядом стоящих участков с одинаковой высотой.
Входные данные
В первой строке дано одно число n (1 ≤ n ≤ 105
) - количество участков. Во второй строке дано n чисел - высоты участков (|hi
| ≤ 1018
).
В третьей строке дано число m (1 ≤ m ≤ 105
) - количество изменений. В следующих m строках дано по два целых числа x и y (1 ≤ x ≤ n, |y| ≤ 1018
) индекс участка, высота которого изменилась, и новое значение высоты для этого участка, соответственно.
Выходные данные
Выведите 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