ボゾソートをシミュレーションする解法では、O(NQ)となり制限時間内に解くことは難しい。
毎回、ソートされているかの判定を行う必要はなく、隣り合う要素の大小関係について、順番が妥当でないものの個数（これをdiffとする）をキープしておけばよい。 変更が行われた要素の前後の要素それぞれについて、大小関係の変化を調べ、diffを調整する。diffが０になったとき、ソート済みと判断できる。
この解法の場合、両端に番兵を置くとことで、境界の判定を楽に書くことができる。
参考文献：4つの言語で解ける 実践プログラミング問題集