ARC125 C - LIS to Original Sequence (600)
$ A_iより小さい値は$ A_iより後ろに登場しないといけない
$ A_iより大きい値は$ A_iより前に登場しないといけない
そうしないと最長増加部分列の長さが1増えてしまう
そのためPの最初の値は$ A_1
その後ろに$ A_1未満の値が降順に並ぶ
降順で無い場合最長増加部分列の長さが増やせてしまう
次は$ A_2が来て$ A_2未満$ A_1より大きい値が降順に並ぶ
これを基本的に$ A_kまで繰り返す
これでは$ A_kより大きい値を置く場所が無いため、$ A_kの前に降順で置く