XOR について、以下の性質が成り立ちます。

• 任意の非負整数 \(x,y,z\ (x<y<z)\) に対して、\(\mathrm{min}(x\oplus y, y\oplus z) < x\oplus z\)

証明： \(x,z\) を \(2\) 進数表記したとき、下から \(k+1\) ビット目以上は一致していて、下から \(k\) ビット目が異なる（\(x<z\) より \(x\) は \(0\) 、\(z\) は \(1\)）とします。 このとき、\(x\oplus z \geq 2^k\) です。

また、\(y\) に着目すると、\(x<y<z\) より \(y\) の下から \(k+1\) ビット目以上は \(x,z\) と一致しています。ここで、 \(y\) の下から \(k\) ビット目が \(0\) ならば、\(x\oplus y < 2^k\)、 \(y\) の下から \(k\) ビット目が \(1\) ならば、\(y\oplus z < 2^k\) が成立することが確かめられます。よって、\(\mathrm{min}(x\oplus y, y\oplus z) < x\oplus z\) が示されました。（証明終わり）

この性質を用いると、黒板に書かれた整数を昇順に並び替えたとき、隣接する値の XOR のみが答えの候補であることがわかります。

黒板に値が追加されたり削除されたりするときの隣接する値の XOR の管理は、std::set などの順序付き集合を用いて実装できます。

具体的には、値を追加するときは、追加した値の前後を答えの候補に加え、値を削除するときは、削除する値との前後を答えの候補から取り除き、削除によって隣接することになったペアを候補に加えればよいです。