\(N\) の偶奇で場合分けします．

\(N\) が偶数の場合：

先頭が \(1,2,\cdots,N/2\) の good な列の個数と \(N/2+1,\cdots,N\) の個数は完全に一致します． よって求める列は，先頭が \(N/2\) の good な列の中で辞書順最大のものです． これは単に，先頭以外の項を降順ソートして得られる列です．

\(N\) が奇数の場合：

先頭が \(1,2,\cdots,(N-1)/2\) の good な列の個数と \((N+3)/2,\cdots,N\) の個数は完全に一致します． よって，答えとなる列の先頭は \((N+1)/2\) になります． そして，残った要素を並べてできる列の中で辞書順がちょうど真ん中のものを求めればよいです． そこで先頭から \(2\) 番目の値について考えてみます． \((N+1)/2\) が残っているなら，先頭と同じ議論を行うことができ，先頭から \(2\) 番目は \((N+1)/2\) とわかります．

結局，先頭 \(K\) 項は\((N+1)/2\) になります． 残りの部分は \(N\) が偶数の場合と全く同じになるので，この場合も解決することができました．

上記の手順をそのまま実装すると \(O(NK)\) 時間解法になります．

回答例(C++)