（列に対しての）平方分割による解法を紹介します．

ブロックには次の要素を持たせます．

• ソートされた，高々 \(B\) 個からなる数列
• その数列における奇数要素の総和，偶数要素の総和

また，ブロックを順に並べ \(1,2,\dots,\lceil \frac{Q}{B} \rceil \) としたとき，「ブロック \(i\) が持つ要素の最大値 \(\leq \) ブロック \(i+1\) が持つ要素の最小値」を満たすようにします．

これが分かっていれば，クエリで答えるべき値は \(O(\frac{Q}{B})\) で簡単にわかります．

よって，上に示した条件を満たしながら，高速に値を挿入できれば良いです．

ソートされた高々 \(B\) 個の数列の要素を deque によって持ちます．

\(X\) を挿入したいとしましょう．これは以下のような手続きによりできます．

1. \(X\leq\) ブロック \(i\) が持つ要素の最大値 となるような最小のブロック \(i\) に \(X\) を挿入する．（ブロック \(i\) の要素数が \(B\) に満たない場合はブロック \(i\) が持つ要素の最大値 \(= \infty\) とする．）
2. ブロック \(i\) の要素数が \(B\) より大きくなった場合，次の操作を行う．
   • 変数 \(T\) をブロック \(i\) における最大値と定め，ブロック \(i\) から \(T\) を削除する．
   • ブロック \(j=i+1,\dots,\) の順に 以下を行う．
   • ブロック \(j\) に \(T\) を挿入する．
   • ブロック \(j\) の要素数が \(B\) より大きくなった場合，変数 \(T\) をブロック \(i\) における最大値と定め，ブロック \(i\) から \(T\) を削除する．
   • そうでない場合，2. から抜ける．

ソートされた高々 \(B\) 個の数列の要素を deque によって持っておけば，1.の操作は 愚直に行うことで \(O(B)\) ，2.の全ての操作は \(1\) ブロック当たり\(O(1)\) で実行可能です．(2. で扱う値はブロックにおける最大値，最小値なので deque によって \(O(1)\) で処理できることに注意してください．)

したがって，\(B=\Theta (\sqrt Q)\) とすることでこの問題を 時間計算量 \(O(Q \sqrt Q)\) ，空間計算量 \(O(Q)\) で解けます．