[1] A necessary condition

For a solution to exist, \(N\geq 2K\) is necessary. Indeed, one can choose \(A_K\) so that \(1\leq A_K\leq N\) and \(|A_K-K| \geq K\) only if \(N\geq 2K\).

Below, let us check whether a solution exists under this necessary condition.

---

[2] An unsuccessful greedy algorithm

Since the problem asks for the lexicographically minimum, one can come up with the following greedy algorithm:

For each \(i=1,2,3,\ldots\) in this order, do the following: let \(A_i\) be the smallest integer \(x\) such that \(\lvert x - i\rvert \geq K\) among the numbers not in \(A_1, \ldots, A_{i-1}\).

However, it fails. Indeed, in Sample Input 2, the optimal solution chooses \(A_4 = 7\), although \(x = 1\) satisfies \(\lvert x - 4\rvert\geq 3\). Why?

When constructing the permutation, one must certainly set \(A_i\) for all \(i\), but one must also set \(i\) such that \(A_i = x\) for all \(x\). For instance, in Sample Input 2, the \(i\) such that \(A_i = 7\) must satisfy \(i\leq 4\). This will explain why one must choose \(A_4 = 7\) in the optimal solution.

---

[3] A successful greedy algorithm

Based on the lesson from [2], let us try another greedy algorithm:

For each \(i=1,2,3,\ldots\) in this order, do the following:

• If \(j = i+K\) is not in \(A_1, \ldots, A_{i-1}\), and \(j > N - K\), let \(A_i = j\).
• Otherwise, let \(A_i\) be the smallest integer \(x\) such that \(\lvert x - i\rvert \geq K\) among the numbers not in \(A_1, \ldots, A_{i-1}\).

It is not clear that this algorithm successfully determines a permutation (that is, it never happens that no \(x\) is available), but if it does, the output is optimal because of the argument in [2].

---

[4] The output of the greedy algorithm

Let us confirm that the algorithm in [3] works.

First, when \(2K\leq N\leq 4K\), one can verify that the algorithm returns the following permutation \(A\):

When \(2K\leq N\leq 3K\)

\[ A_i = \begin{cases} i + K & (1\leq i \leq N-K) \\ i - N + K & (N-K < i\leq N) \end{cases} \]

When \(3K < N \leq 4K\)

\[ A_i = \begin{cases} i+K &(1\leq i \leq K)\\ i-K &(K<i\leq N-2K)\\ i + K &(N-2K< i\leq N-K)\\ i-2K &(N-K < i \leq 3K)\\ i-K &(3K < i \leq N) \end{cases} \]

When \(N\geq 4K\), the algorithm begins by printing \((K+1, \ldots, 2K, 1, \ldots, K)\) as the first \(2K\) terms and then run in the same way as in the case of \(N-2K\), so it can be inductively deduced that the algorithm does print a solution.

Therefore, the problem can be solved in \(O(N)\) time by properly implementing the algorithm in [3] or using the formulae above.

---

[5] FYI: the solutions for \(K=4\)

Here are samples of the solutions for \(K = 4\):

• \(N=8\): \((5,6,7,8,1,2,3,4)\)
• \(N=9\): \((5,6,7,8,9,1,2,3,4)\)
• \(N=10\): \((5,6,7,8,9,10,1,2,3,4)\)
• \(N=11\): \((5,6,7,8,9,10,11,1,2,3,4)\)
• \(N=12\): \((5,6,7,8,9,10,11,12,1,2,3,4)\)
• \(N=13\): \((5,6,7,8,1,10,11,12,13,2,3,4,9)\)
• \(N=14\): \((5,6,7,8,1,2,11,12,13,14,3,4,9,10)\)
• \(N=15\): \((5,6,7,8,1,2,3,12,13,14,15,4,9,10,11)\)
• \(N=16\): \((5,6,7,8,1,2,3,4,13,14,15,16,9,10,11,12)\)
• \(N=17\): \((5,6,7,8,1,2,3,4,13,14,15,16,17,9,10,11,12)\)
• \(\vdots\)