問題

座標 $X$ にイチゴの乗った長さ $L$ のケーキに対して、 $i (1 \leq i \leq N)$ 回目の操作後のケーキの美しさを求める。

操作は、 * 座標 $A_i$ にイチゴがないなら、座標 $A_i$ にイチゴを乗せる * 座標 $A_i$ にイチゴがあるなら、座標 $A_i$ のイチゴを取り除く

ケーキの美しさは、次の値の最大値として定義する。 1. 0個以上のイチゴの座標 $x$ を座標 $L-x$ に移動する（座標 $L-x$ にイチゴがあるときは移動できない） 2. 移動後のもっとも近い2つのイチゴの最小値を求める

考察

座標 $L-x$ にあるイチゴは座標 $x$ に移動する。座標 $x, L-x$ にあるイチゴは同じ位置にあるものと考え、全てのイチゴの座標 $x$ から $\min(x, L-x) (\leq \frac{L}{2})$ へ移動する。ここで、同じ座標に2つのイチゴがあることは、一旦いいものとする。これで、全てのイチゴの（座標 $\frac{L}{2}$ 以下になった。

移動後のイチゴの座標を昇順に並べて、 $x_1, x_2, \cdots, x_n$ とする。連続する3つのイチゴのうち、少なくとも2つは半分に割った時の同じ側にいるので、これらの3つの座標 $x_i, x_{i+1}, x_{i+2}$ の差の最小値の最大値は $x_{i+2} - x_i$ である。帰納的に、全てのイチゴを昇順に並べたあと、奇数番目はそのまま、偶数番目は $L-x$ へ移動するのがいいことがわかる。また、中心軸を挟んだ両はしにあるイチゴは隣り合っているので、 $(L - x_n) - x_{n-1}$ も最小距離の候補になる。

イチゴを1つ追加するときの操作を考える。座標 $b_1, b_2, b_3, b_4 (b_1\leq b_2\leq b_3\leq b_4)$ とイチゴが並んでいるとき、上記の移動後の2つのイチゴの距離は、 $b_3 - b_1, b_4 - b_2$ である。これに座標 $x$ にイチゴを追加する（ $b_1\leq b_2\leq x \leq b_3\leq b_4$ ）。再び、上記の移動を行うと、2つのイチゴの距離は、 $x - b_1, b_4 - x, b_3 - b_2$ である。これらを追加、削除する。イチゴを削除するときは、この逆の操作を行えばいい。