Ник Фьюри решил, что бойцы отряда спецназа, являющегося подразделением организации 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 |