いやこれ難しすぎるだろ（解けたのすごいね（自画自賛））
とりあえず判定問題を考えないとどうしようもなくて
X - Yの値を値としてもたないと状態が爆発しそう
最小と最大をもとめればその間全部作れるやつでしょ（適当）
最小と最大をDPで求めてそこを高速化できそう
まあ辞書順だし前から見るしかないでしょ 片方の最大値は一意に定まるしもう片方を状態として持てばいいね
まあできそう でも復元できなくない？できない 後ろからやる？無理そう
気を取り直して、こういう形は大きい順か小さい順に挿入DPって義務教育で習った
1 2 3 4 5 （デデドン） 最小は-5、最大は5、0は作れません
最小と最大をもとめればその間全部作れるやつではなかった（かなしいなあ）*1
いやそもそも復元を考えると後ろからやらないと無理でしょ（冷静）
Pで高い要素はXとYのどちらにいったとしても高い要素になるな（発見）
Pで高い要素をらてな要素、らてではない要素をうくな要素とよぼう（現実逃避）
らてな要素が偶数個なら自明に構成できる 奇数個の時の判定問題を考える
うくな要素が高いとき、自由に低くできることがわかる
長さが（らてな要素の数＋１）／２＋１以上の増加列であって、うくな要素を一つ以上含むようなものがあればできそう
判定問題は解けた 一般化すると？
まあ辞書順最小を復元するためにまず後ろから見て前から決めていきたい
ある要素以上の要素からなる要素列であって、それの補集合との高い要素の数の差をなるべく大きくしたい
補集合はなるべく小さくしたい つまり、うくな要素を含める理由がない
このときその集合かららてな要素をひとつ動かすと差が2減って、うくな要素を動かすと1減るから、最大値が0以上ならよさそう
うくな要素が入っているようのdp(dp2)と入っていないようなdp(dp1)を考える
遷移が区間max 区間addになっていて、しかもロールバックができる形 勝ったなガハハ
セグ木を書いておわり*2
