Держать строй

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

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

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

Первая строка входного файла содержит два числа $n$ и $m$ ($1 \le n \le 100{\\,}000$, $0 \le m \le 200{\\,}000$) --- количество солдат в строю и количество команд, которые подаст Ник. Вторая строка содержит $n$ целых неотрицательных чисел, не превосходящих $10^9$ --- исходный рост солдат в строю.

Следующие $m$ строк содержат команды, подаваемые Ником. Если первый символ в строке, описывающей очередную команду, '!', то за ним следуют два числа $k$ и $x$ ($1 \le k \le n$, $0 \le x \le 10^9$), где $k$ --- место в строю того солдата, которого должен заменить солдат роста $x$. Команда второго типа описывается знаком '?'.

Для каждой команды второго типа в отдельной строке выведите <<YES>>, если в данный момент солдаты в строю стоят по неубыванию роста, и <<NO>> --- в противном случае.