Егер \(a_i > a_{i+1}\) позициясы болса, онда егер екі сан да өзгерту сұрағының аралығына түссе, олар бірдей болып қалады (не \(a_i\) тең, не \(a_i\) дейін бірдеңе). Бұдан кейінгі жағдайларда \(a_i\) мен \(a_{i+1}\) бір санға бірігеді деп есептейік. Осылай ойласақ, өзгерістер саны \(n\)-нен көп болмайды.

Блоктарда бірдей сандарды сақтаймыз. Өзгерту сұрағы болғанда, \(a_i > a_{i+1}\) ең сол жақ позицияны табамыз (мұны жиында сақтауға болады) және қажетті мәнді сегменттік ағаш арқылы аралыққа тағайындаймыз. Әр жаңартудан кейін, ең жаманы, бір блок қосылады және біраз блоктар бірігеді. Осыдан блоктардағы өзгерістер саны \(2n\)-нен көп болмайды.

Пусть есть позиция \(a_i > a_{i+1}\). Если оба числа попадут в отрезок запроса изменения, то они оба станут равными (либо равны \(a_i\), либо чему-то до \(a_i\)). Будем считать что после такого запроса мы сливаем \(a_i\) и \(a_{i+1}\) в одно число. Если думать так, то тогда изменений будет не больше чем \(n\).

Будем хранить блоки где числа в блоках одинаковые. При запросе изменения, будем искать самую левую позицию где \(a_i > a_{i+1}\) (можно хранить в сете) и делать присвоение на отрезке необходимого значения через дерево отрезков. После каждого обновления у нас добавится в худшем случае один блок, и какое то количество блоков объединятся, из-за этого суммарно будет не более \(2n\) изменений на блоках.