Олимпиадный тренинг

Задача . Держать строй


Ник Фьюри решил, что бойцы отряда спецназа, являющегося подразделением организации S.H.I.E.L.D., помогут мстителям отразить атаку войска Локи. Он решил, что в бой отправятся n бойцов, а все остальные понадобятся в других местах. Теперь ему осталось только выбрать, какие именно бойцы пойдут в атаку.

Сначала Ник выбрал n бойцов случайным образом и выстроил их в линию, а затем стал по одному заменять кого-то из уже выбранных бойцов на другого солдата, который в настоящее время в строю не стоит. Поскольку отряд достаточно большой, Ник не знает каждого бойца лично.  Оценить боеспособность отряда он может разве что по каким-нибудь заметным внешним признакам. Важным показателем боеспособности отряда является, например, то, стоят ли солдаты в строю по неубыванию роста.

Так, Ник может давать команды двух видов. Первая команда заключается в том, что новый солдат роста x встает в строй вместо солдата, стоящего на k-ом месте. Подавая вторую команду,  он хочет узнать, стоят ли солдаты в строю по неубыванию роста. Ваша задача обрабатывать эти команды и сообщать в ответ на запросы то, что хочет узнать Ник.

Формат входного файла
Первая строка входного файла содержит два числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000)  количество солдат в строю и количество команд, которые подаст Ник. Вторая строка содержит n целых неотрицательных чисел, не превосходящих 109  исходный рост солдат в строю. Следующие m строк содержат команды, подаваемые Ником. Если первый символ в строке, описывающей очередную команду, '!', то за ним следуют два числа k и x (1 ≤ k ≤ n, 0 ≤ x ≤ 109), где k  место в строю того солдата, которого должен заменить солдат роста x. Команда второго типа описывается знаком '?'.

Формат выходного файла
Для каждой команды второго типа в отдельной строке выведите "YES", если в данный момент солдаты в строю стоят по неубыванию роста, и "NO"  в противном случае.
 
Ввод Вывод
5 5
2 4 6 8 10
?
! 2 7
?
! 3 8
?
YES
NO
YES

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w648
Java2
Комментарий учителя