Дата сайнс
(Время: 2 сек. Память: 32 Мб Сложность: 64%)
Назовём последовательность чисел xi пилообразной, если x1 > x2 < x3 > x4 < … или x1< x2 > x3 < x4 > … (заметим, что последовательность из одного числа и последовательность из двух различных чисел являются пилообразными).
Назовём хаотичностью последовательности xi наибольшее число k такое, что можно удалить некоторые числа из x и оставшиеся будут образовывать пилообразную последовательность размера k.
Михаилу, начинающему дата-саентисту, необходимо обработать данные, представленные в виде массива n различных чисел ai. Есть два типа запросов к данным:
- «! i x» – установить ai равным x (гарантируется, что после этого все ai будут различны);
- «? l r» – вычислить хаотичность отрезка a[l…r], то есть последовательности al, al+1, …, ar;
По загадочным обстоятельствам Михаил больше не будет программировать алгоритмы, поэтому ему нужна ваша помощь в обработке данных.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n – размер данных (1 ≤ n ≤ 2×105).
Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 109).
Третья строка содержит целое число q – количество запросов (1 ≤ q ≤ 3×105).
В каждой из следующих q строк содержится описание запроса в формате, описанном выше. Для запросов изменения выполняется 1 ≤ i ≤ n и 1 ≤ x ≤ 109. Для запросов на отрезке выполняется 1 ≤ l ≤ r ≤ n.
Гарантируется, что в любой момент a состоит из попарно различных чисел.
Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса второго типа (то есть начинающегося с «?») в порядке их поступления на вход выведите в новой строке одно целое число – ответ на этот запрос.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 6
1 6 2 5 3 4
7
? 1 6
? 2 5
! 1 9
! 4 1
? 1 4
! 1 5
? 1 6 | 6
4
2
4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|