Permutation p is an ordered set of integers p1, p2, ..., pn, consisting of n distinct…
- User
Permutation p is an ordered set of integers p1, p2, ..., pn, consisting of n distinct positive integers not larger than n. We'll denote as n the length of permutation p1, p2, ..., pn.
Your task is to find such permutation p of length n, that the group of numbers |p1 - p2|, |p2 - p3|, ..., |pn - 1 - pn| has exactly k distinct elements. Input
The single line of the input contains two space-separated positive integers n, k (1 ≤ k < n ≤ 105).
Output
Print n integers forming the permutation. If there are multiple answers, print any of them.
Examples
Input
3 2
Output
1 3 2
Input
3 1
Output
1 2 3
Input
5 2
Output
1 3 2 4 5
Note
By |x| we denote the absolute value of number x.
Assistant
We need to construct a permutation of numbers 1..n such that the absolute differences between consecutive elements (there are n-1 differences) take exactly k distinct values. Input constraints: n up to 1e5, k < n. We need to output any such permutation.
Goal: For given n,k, produce a permutation p such that the set { |p_i - p_{i+1}| : i=1..n-1 } has size exactly k.
We can think about constructing such a permutation. There's known problem: "Permutation with given number of distinct adjacent differences" maybe similar to Codeforces problem "Permutation" or something. Let's reason.
We have n numbers. Differences are between 1 and n-1 (since max difference between two distinct numbers from 1..n is n-1). However, they can be any values from 1 to n-1. We need exactly k distinct values.
We need to produce a permutation that uses exactly k distinct differences. Note that maximum number of distinct differences we can have is n-1 (if all differences are distinct). But we need exactly k, which is less than n (k<n). So we need to reduce distinct differences.
One approach: Start with an ordering that yields many differences, then modify to collapse some differences into duplicates. Alternatively, construct explicitly a pattern that yields exactly k distinct differences.
Observation: If we take a permutation that alternates high and low numbers, we can get many large and small differences. But we need control.
Consider constructing a permutation as follows: Let the differences we want to use be d1, d2, ..., dk (some set of k distinct integers from 1 to n-1). We need to arrange the numbers such that the consecutive differences are only these values, and each used at least once. And we need to use all numbers 1..n exactly once.
We can try to build a path (permutation is a Hamiltonian path on the complete graph labeled 1..n) with edge weights being absolute differences. The set of edge weights used should be exactly k. So we need a Hamiltonian path that uses only k distinct edge weights. This is reminiscent of constructing a permutation where differences are like 1,2,...,k but some repeated etc.
Perhaps we can use a simple construction: For any n and k, we can produce a permutation like:
Let’s consider using differences 1,2,...,k? But we have n-1 edges, so we need to repeat some differences. So we can use exactly k distinct differences: 1,2,...,k? Is that always possible? Let's test small: n=3,k=2 -> differences 1 and 2. The example 1 3 2 yields differences 2 and 1, so yes. n=3,k=1 -> differences all 1? But example 1 2 3 yields differences 1 and 1, distinct set {1} -> yes. n=5,k=2 -> example 1 3 2 4 5 yields differences: 2 (1-3=2), 1 (3-2=1), 2 (2-4=2), 1 (4-5=1) -> distinct {1,2} -> yes.
So they used differences 1 and 2. That suggests a simple pattern: alternate between 1 and 2 differences? More generally, perhaps we can use differences: 1,2,...,k, then repeat some of them to fill the rest edges.
But can we always construct such a permutation for any n and k? Let's think.
We need to ensure that the numbers used are exactly 1..n. So we need to produce a sequence that covers all numbers exactly once.
Consider constructing a "zigzag" sequence: start with 1, then add k, then subtract (k-1), then add (k-2), etc. That's like: 1, 1+k, 1+k-(k-1)=2, 2+(k-2)=? Wait.
Actually, we can produce a sequence that uses differences 1,2,...,k in a pattern that covers all numbers from 1 to something. For example, for n = something, we can create a permutation that is a "mountain" shape.
I recall a known construction for this problem (I think it's Codeforces Round #319 Div. 2 Problem C? Actually I recall a problem: "Permutation" from Codeforces 359 B? No). Let's think.
We can treat the numbers as positions on a line. Differences are distances. We need to have exactly k distinct distances. One idea: Use a permutation that consists of a block of consecutive numbers arranged in some pattern plus a block of other numbers.
Alternatively, consider building the permutation by starting at 1, then jumping by k, then by k-1, then by k, etc? Not sure.
Simplify: Let's try to construct for any n, k, the following: Use the set of differences = {1,2,...,k}. And we will create a permutation that uses each of these differences at least once and no others. Since we have many edges (n-1), we will repeat them. We need to ensure the numbers used are 1..n.
Is it always possible to construct a permutation of 1..n using only differences from {1,...,k}? Not necessarily if k is small relative to n, because the range of numbers is n, and the maximum step is k. Starting from some number, using steps of at most k, can we reach all numbers? The maximum difference we can take is k, but the numbers are spread over a range of n-1. To go from min to max (distance n-1), we would need a cumulative sum of steps that covers that range. But steps are absolute differences; they represent the change from one number to the next. So if we start at some number, after a sequence of steps, the current value can be anywhere between 1 and n. Since steps are bounded by k, the total variation from start could be limited? However, steps can be in positive or negative direction (since permutation ordering doesn't require monotonicity). So we can move up and down. So with steps up to k, we could still cover a wide range by accumulating ups and downs. But can we achieve all numbers? Possibly yes.
Consider k=1. Then only difference allowed is 1. The permutation must have consecutive numbers differing by exactly 1. That means the permutation is a sequence where each step moves to an adjacent integer. That's exactly a "path" that visits all numbers, which is essentially a permutation that is a monotonic sequence (either increasing or decreasing) or maybe with some back-and-forth? But if each step is 1, then the sequence must be a Hamiltonian path on the integer line where each edge connects i and i+1. That means it's a sequence that moves only by +1 or -1 each step, and cannot skip any numbers? Actually, if you only move by 1, you can only go to adjacent numbers. Starting from some number, you can eventually visit all numbers? For n numbers, you need to traverse all vertices of a path graph (1-2-3-...-n). This graph is a line. A Hamiltonian path that visits each vertex exactly once exists, e.g., 1,2,3,...,n (increasing) or decreasing. So for k=1, it's possible. So using only difference 1 works.
Now for k=2. Differences allowed: 1 and 2. Can we visit all numbers from 1 to n using steps of 1 or 2? This is like a path on the integer line where edges connect numbers with absolute difference 1 or 2. This graph is more connected. Does it have a Hamiltonian path? Since the graph includes edges between i and i+1 and i and i+2. That graph is basically a "ladder" but on a line; it's basically a path augmented with chords. It should be Hamiltonian for all n (I think). Indeed, there is a known pattern: 1,3,2,4,5,... or something. So yes.
For general k, the graph where edges exist between numbers with difference ≤ k is a "unit interval graph"? Actually it's like a complete graph on numbers? No, only differences up to k. That is a graph on vertices 1..n with edges connecting i and j if |i-j| ≤ k. This graph is called a "band graph". For k>=1, it is connected. Does it have a Hamiltonian path? Since the graph is essentially a "path" with extra edges, it might always have a Hamiltonian path (obviously any connected graph on n vertices has a Hamiltonian path? Not necessarily, but this graph is "chordal" and maybe yes). But the Hamiltonian path existence is not guaranteed for all connected graphs; however, this specific graph is "interval graph" and is known to be "Hamiltonian" if it is connected? Actually, not all interval graphs are Hamiltonian? Wait, a simple connected graph on vertices 1..n with edges between i and j if |i-j| ≤ k is basically a "k-th power of a path graph". The k-th power of a path graph is known to be Hamiltonian for all n when k≥1? The square of a path (k=2) is known to be Hamiltonian (every square of a connected graph is Hamiltonian under some conditions? Actually, the square of a graph is the graph obtained by adding edges between vertices at distance at most 2. The square of a path is definitely Hamiltonian because you can use the natural order 1,2,...,n; but that order may not be a Hamiltonian path in the square? Wait, in the square of a path, edges exist between vertices that are at most 2 apart in the original path. So 1 is connected to 2 and 3. 2 to 1,3,4. etc. So the natural order 1,2,3,...,n uses edges between consecutive numbers which are all present (since difference 1 ≤2). So indeed the natural order is a Hamiltonian path. For any k>=1, the natural increasing order uses edges of difference 1, which are allowed (since 1 ≤ k). So the increasing sequence 1,2,...,n is a Hamiltonian path in the graph with edges up to k (since all consecutive differences are 1). So indeed the graph contains the path 1-2-...-n because all these edges are present (difference 1). So any k>=1, the increasing sequence is a valid permutation if we only require edges to be within allowed differences? But wait, the requirement is that the set of absolute differences must be exactly k distinct values. So if we use only difference 1, then the set size is 1, not k (unless k=1). So we need to include differences up to k, but we can also include smaller ones; but we must ensure that the set of differences used equals exactly k. So we must use all values 1,...,k at least once? Actually exactly k distinct values, but they don't have to be exactly 1..k; they could be any set of size k. However, a simple construction uses 1..k because it's easy.
Thus the increasing sequence only gives difference 1, so set size 1. That's not enough when k>1. So we need to incorporate other differences as well, while still staying within the graph (i.e., all steps allowed? Actually there's no restriction that steps must be ≤ k; we can use any difference because we are free to choose any permutation; the graph analogy is only for if we restrict ourselves to differences ≤ k. But we don't have to restrict to ≤ k; we could use larger differences, but then those would be additional distinct values, increasing the set size beyond k. So to keep exactly k distinct values, we need to avoid differences outside the chosen set. So if we choose the set to be {1,2,...,k}, then we must ensure that all steps have absolute difference in {1,...,k}. That means we cannot use a step of difference > k. So the increasing sequence uses only difference 1, which is allowed, but we also need to include differences 2,...,k at least once, and we must not use any difference outside {1,...,k}. So we need a Hamiltonian path on the graph where edges have weight ≤ k (which is the same graph) but we need to use each weight 1..k at least once. The increasing sequence is a Hamiltonian path but uses only weight 1. But we can modify it to incorporate larger steps.
Now, is it always possible to find a Hamiltonian path on the "k-th power of the path" that uses each edge weight (1..k) at least once? Possibly yes. But we also need to ensure that no other weights appear (i.e., we don't accidentally create a difference > k). Since all edges in that graph have difference ≤ k, any Hamiltonian path in that graph will automatically satisfy that all differences are ≤ k. So the set of distinct differences will be a subset of {1,...,k}. So we need to ensure that the set is exactly {1,...,k} (or any set of size k). So the problem reduces to: find a Hamiltonian path in the graph G_n,k (vertices 1..n, edges between i and j if |i-j| ≤ k) such that the edge weights (|i-j|) used cover all values 1..k. That's the construction.
Now, is there always such a Hamiltonian path? For k=1, G_n,1 is just the path graph itself; the only edge weights possible are 1. So covering {1} is trivial (the increasing sequence works). For k=2, G_n,2 is the square of the path. We need a Hamiltonian path that uses both differences 1 and 2. Does such a path always exist? For n=3, yes: 1,3,2 (differences 2,1). For n=4, can we? Example: 1,3,2,4 gives differences: 2,1,2 -> set {1,2}. So works. For n=5, example: 1,3,2,4,5 gives 2,1,2,1 -> works. For n=2? k< n so n≥2, but k≥1? For n=2,k=1, the only permutation: 1,2 (diff 1). So works. For n large, can we always construct? Let's try n=6,k=2. We need a permutation using differences 1 and 2 only. Maybe 1,3,2,4,5,6? differences: 2,1,2,1,1 -> set {1,2} works. But wait check: after 5 to 6 diff 1. So okay. So pattern: start with 1, then alternate adding 2 and subtracting 1? Actually 1 -> 3 (+2), 3 -> 2 (-1), 2 -> 4 (+2), 4 -> 5 (+1) not +2? That's okay. But we need to ensure all numbers 1..6 appear exactly once. The pattern 1,3,2,4,5,6 covers all. But note that after 4 we used +1 to get 5. That's allowed. So seems possible.
General pattern for k=2: we could do: 1,3,2,4,5,6,...,n. This uses differences: between 1 and 3:2, between 3 and 2:1, between 2 and 4:2, between 4 and 5:1, then 5-6:1, etc. So the set is {1,2}. So it works for any n≥3. For n=2, k=1 only, not applicable. So good.
Now for k=3: Need differences {1,2,3}. Can we construct? Let's attempt to find a pattern. For n=4, k=3? But k<n, n=4,k could be 3. Need permutation of 1..4 with diffs exactly {1,2,3}. There are 3 differences. Example: 1,4,2,3 gives diffs: 3,2,1 -> set {1,2,3}. Works. For n=5,k=3: need permutation using only {1,2,3} and covering all 5 numbers. Try to extend pattern: 1,4,2,5,3? Let's compute diffs: 1-4:3, 4-2:2, 2-5:3, 5-3:2 -> set {2,3} missing 1. Not good. Maybe 1,4,2,3,5? diffs: 3,2,1,2 -> set {1,2,3} good? Check: 1-4=3, 4-2=2, 2-3=1, 3-5=2 -> set {1,2,3}. Yes. So works. For n=6,k=3: try 1,4,2,5,3,6? diffs:3,2,3,2,3 -> set {2,3} missing 1. So need 1 somewhere. Could do: 1,4,2,3,5,6? diffs:3,2,1,2,1 -> set {1,2,3} works? Check: 1-4=3,4-2=2,2-3=1,3-5=2,5-6=1 -> yes. So pattern: start with 1, then jump by k (i.e., 1 to 1+k), then go down by (k-1) to 2, then up by k? Wait. For k=3: 1,4 (diff 3), then 2 (diff 2), then 3 (diff 1), then 5 (diff 2), then 6 (diff 1) etc. That seems to produce differences 3,2,1,2,1,... So includes all three. For larger n, continue with +2, +1 pattern after covering up to maybe? Actually after we have placed numbers 1,2,3,4,5,6,... we can just continue with increasing sequence after some point? Let's see: The pattern: 1, k+1, 2, k+2? Not exactly.
General construction idea: We want to include differences 1,2,...,k. A known approach: create a permutation that "alternates" between the low and high ends, generating large differences initially, and then fill the middle with small differences.
Consider the following approach: first, produce a sequence that uses all differences from 1 to k exactly once, and then fill the rest with difference 1 (or something) to keep total distinct values exactly k. But we must ensure that we don't introduce new differences beyond k.
A simple construction found online (I recall Codeforces problem "C. Permutation" maybe from #281 Div2?): The answer is: start with 1, then for i from 2 to k+1, alternately place numbers from the two ends. Actually, I think a known solution: For given n and k, we can output: 1, k+1, 2, k, 3, k-1, ... and then the remaining numbers in increasing order. Let's test for n=5,k=2: that would be: 1, 3, 2,? Actually following: 1, k+1=3, 2, k? But k=2, so next would be? The alternating pattern: after 1,3,2, then maybe next is? If we continue: we might get 1,3,2,? 2 already used. So maybe pattern: 1, k+1, 2, k, 3, k-1,... but that would use numbers from both ends. For k=2: 1,3,2,? Next would be k? Actually k=2 but 2 already used. So we stop. Then remaining numbers: 4,5 in increasing order. So permutation: 1,3,2,4,5. That's exactly the sample! Good.
For k=3, n=6: start 1,4,2,3? Let's see: pattern: 1, k+1=4, 2, k=3, 3, k-1=2? But 2 and 3 already used. So after 1,4,2,3 we have used 1,2,3,4. Remaining numbers: 5,6 in increasing order -> permutation: 1,4,2,3,5,6. Check differences: 1-4=3, 4-2=2, 2-3=1, 3-5=2, 5-6=1 -> set {1,2,3}. Works. For n=7,k=3: used numbers 1,4,2,3? Then remaining 5,6,7 in increasing: 1,4,2,3,5,6,7. Differences: 3,2,1,2,1,1 -> set {1,2,3}. Works. For n=4,k=3: used numbers: 1,4,2,3? That's exactly all numbers: 1,4,2,3. Differences: 3,2,1 -> set {1,2,3}. Works. So this pattern seems to work: first, create a "zigzag" between 1 and k+1: start with 1, then k+1, then 2, then k, then 3, then k-1, ... but actually we only need to generate the first k+1 numbers in a special order. Let's formalize:
Let’s define a sequence of length (k+1) as follows: We have two pointers: L = 1, R = k+1. We will produce a sequence: start with L=1, then R, then increment L, then decrement R, then increment L, then decrement R, ... until we have included all numbers from 1 to k+1. Actually, after some steps we will have L and R crossing. But note that the numbers from 1 to k+1 inclusive are exactly k+1 numbers. If we alternate L and R, we will produce all of them. For example, for k=3 (k+1=4): L starts 1, R starts 4. Sequence: 1 (L), 4 (R), then L becomes 2 -> 2, then R becomes 3 -> 3. So we get 1,4,2,3. That's exactly the pattern. For k=2: L=1,R=3 -> sequence: 1,3,2 (since after that L becomes 2, R becomes 2? Actually after using R=3, L becomes 2, then we could use L=2? But if we try to continue: after 1,3, we would next L=2, then R=2, but 2 is already used. So we stop when all numbers from 1 to k+1 are used. So the sequence naturally ends when L > R? Actually we can generate by: for i from 1 to k+1: if i is odd, take the smallest not used; if i is even, take the largest not used from the set {1..k+1}. That yields the pattern.
Thus the construction: The first (k+1) numbers of the permutation are arranged as: take alternately from the left and right ends of the range [1, k+1]. So we get: 1, k+1, 2, k, 3, k-1, ... This sequence will have differences that include k, k-1, ..., 1? Let's verify: Differences between consecutive numbers in this prefix: Between 1 and k+1: difference k. Between k+1 and 2: difference (k+1 - 2) = k-1. Between 2 and k: difference k-2. Between k and 3: difference k-3. ... Eventually, the last difference will be between some two numbers that are consecutive in the natural order, which will be 1? Actually, if k+1 is even or odd? Let's compute the differences precisely. The prefix sequence of length m = k+1. Write it as: p1, p2, ..., p_{k+1}. We have: p1 = 1. p2 = k+1. p3 = 2. p4 = k. p5 = 3. p6 = k-1. ... General: For i from 1 to k+1: If i is odd: p_i = (i+1)/2 (since odd positions: 1st->1, 3rd->2, 5th->3,...) If i is even: p_i = (k+1) - (i/2) + 1? Let's derive: Even positions: 2nd: k+1, 4th: k, 6th: k-1,... So for even i=2j, p_{2j} = (k+1) - (j-1) = k+2 - j? Let's do j=1 -> p2 = k+1; j=2 -> p4 = k; j=3 -> p6 = k-1; so formula: p_{2j} = k+2 - j. So for j from 1 to floor((k+1)/2)? The last even index depends on parity.
Now compute differences: For each i from 1 to k (since we have k differences in this prefix), compute d_i = |p_i - p_{i+1}|. For odd i = 2j-1 (j>=1): p_{2j-1}=j, p_{2j}= k+2 - j? Actually for i=2j-1, then p_i = j, p_{i+1}=p_{2j}= k+2 - j. So d_{2j-1} = (k+2 - j) - j = k+2 - 2j. This ranges from when j=1: k; j=2: k-2; j=3: k-4; etc. So we get differences: k, k-2, k-4, ... down to either 1 or 0 depending on parity. For even i = 2j (j>=1): p_i = k+2 - j, p_{i+1}=p_{2j+1}= j+1 (since next odd). So d_{2j} = |(k+2 - j) - (j+1)| = |k+1 - 2j| = k+1 - 2j (since k+1 >= 2j typically). For j=1: d2 = k-1; j=2: d4 = k-3; j=3: d6 = k-5; ... So the even differences are k-1, k-3, k-5,...
Thus the set of differences in the prefix is: {k, k-1, k-2, ..., 1}? Let's see: We get k (from i=1), k-1 (from i=2), k-2 (from i=3), k-3 (from i=4), ... and so on. Indeed, the differences alternate between decreasing even and odd steps, covering all integers from k down to 1? Let's list for k=4: prefix length 5: sequence: 1,5,2,4,3. Differences: 1-5=4, 5-2=3, 2-4=2, 4-3=1 -> set {4,3,2,1}. Yes exactly all. For k=5: prefix length 6: sequence: 1,6,2,5,3,4. Differences: 5,4,3,2,1? Compute: 1-6=5, 6-2=4, 2-5=3, 5-3=2, 3-4=1 -> set {5,4,3,2,1}. So indeed the prefix of length k+1 yields all differences from 1 to k. Good.
Now, after that prefix, we have used numbers 1..(k+1). The remaining numbers are from k+2 to n. We can simply append them in increasing order. That will introduce differences between the last number of the prefix (which is something) and the first remaining number (k+2) and then consecutive differences of 1 among the rest.
What is the last number of the prefix? Let's determine based on parity of k. For k even: k+1 is odd. The prefix length = odd. The pattern: For k even, say k=2m, then k+1=2m+1 (odd). The sequence of length 2m+1: we will have an odd number of elements. The last element (odd index) will be from the left side. Specifically, after alternating, the final element when all numbers from 1 to 2m+1 are used will be? Let's simulate: k=2 (even): sequence 1,3,2 -> last=2 (which is floor((k+2)/2)?). k=4 (even): 1,5,2,4,3 -> last=3. So for even k, last = (k+2)/2? Actually k=4 => last=3 = (4+2)/2 =3. k=2 => last=2 = (2+2)/2=2. So last = (k+2)/2 = k/2 +1. For odd k: say k=3 (odd): sequence 1,4,2,3 -> last=3. k=5: sequence 1,6,2,5,3,4 -> last=4? Let's list: 1,6,2,5,3,4. Last=4. (k+1)=6 (even length). For odd k, k+1 is even, so the prefix length is even. The last element is from the right side? For k=3, last=3 (which is k). For k=5, last=4 (which is k-1?). Let's compute formula: k=5, last=4 = (k+3)/2? (5+3)/2=4. k=3: (3+3)/2=3. So for odd k, last = (k+3)/2? Actually (3+3)/2=3, (5+3)/2=4, (1+3)/2=2 (but k=1 prefix length 2: sequence 1,2? Actually k=1: prefix length 2, sequence 1,2? According to pattern: start 1, then k+1=2, then? That's all, so last=2. (1+3)/2=2, correct). So last = floor((k+2)/2)+1? Let's derive simpler: The set of numbers used is 1..k+1. The prefix arrangement yields a specific order. The last number is either the median or something. But we care about the difference between the last prefix number and the first remaining number (k+2). That difference could be something. We must ensure that this difference is ≤ k, because we don't want to introduce a new difference > k. Since we are appending numbers from k+2 upward, and the last prefix number is some value between 1 and k+1, the difference to k+2 will be at most (k+2 - 1) = k+1? Actually max possible is if last=1, then diff = (k+2)-1 = k+1, which is > k if k+1 > k, i.e., always > k? k+1 is exactly one more than k. So if last=1, diff = k+1, which is a new distinct difference, increasing the set size to k+1, which is not allowed. So we must avoid that. Similarly, if last is 2, diff = k, which is allowed (already in set). If last is larger, diff smaller, all ≤ k. So we need the last prefix number to be at least 2, i.e., not 1. Is it ever 1? The last element of the prefix is never 1 because 1 is used first. Could it be 1? Only if the prefix ends with 1, but 1 is used at the start. After using 1, it won't appear again. The last element is some other number. Let's check for small k:
k=1: prefix: 1,2 -> last=2. diff to 3? n could be >2? For n=3,k=1, after prefix we have number 3. Then permutation: 1,2,3. Diff between last prefix (2) and 3 is 1, which is ≤1 (allowed). Good.
k=2: prefix: 1,3,2 -> last=2. diff to 4 is 2, which is ≤2 (allowed). Good.
k=3: prefix: 1,4,2,3 -> last=3. diff to 5 is 2, ≤3. Good.
k=4: prefix: 1,5,2,4,3 -> last=3. diff to 6 is 3, ≤4. Good.
k=5: prefix: 1,6,2,5,3,4 -> last=4. diff to 7 is 3, ≤5. Good.
k=6: prefix length 7: let's construct: 1,7,2,6,3,5,4? Actually pattern: 1, k+1=7, 2, 6, 3, 5, 4. Last=4. diff to 8 is 4 ≤6. Good.
So last seems to be either floor((k+2)/2) or something that is >=2 for all k>=1? For k=1, last=2; for k=2, last=2; for k=3, last=3; for k=4, last=3; for k=5, last=4; for k=6, last=4; So last is ceil((k+1)/2)+? Actually for even k=2m, last=m+1? For k=2, m=1, last=2 = 1+1=2. For k=4, m=2, last=3 = 2+1=3. For odd k=2m+1, last = m+2? For k=3 (m=1), last=3 = 1+2=3. For k=5 (m=2), last=4 = 2+2=4. So last = floor(k/2) + 2? Actually for k=2 (floor(2/2)=1) +2 =3, but last=2, not 3. So not.
Better compute: For k even: k=2m, then numbers 1..2m+1. The sequence: left-right alternating until all used. Since there are odd number of elements, the last will be from the left side after some steps. The left side after m steps? Let's simulate: We start L=1, R=2m+1. After each pair, we increment L and decrement R. After m pairs (i.e., 2m elements), we would have used L from 1 to m, and R from 2m+1 down to m+2? Actually, after using 2m numbers: positions: odd indices up to 2m-1? Actually easier: The numbers used as left (odd positions) are: 1,2,3,...,? The numbers used as right (even positions) are: 2m+1,2m,2m-1,... After 2m numbers, we have used left numbers 1..m, and right numbers (2m+1) down to (2m+1 - (m-1)) = m+2? Wait: For m=2 (k=4), after 2m=4 numbers we have: odd positions: 1st:1, 3rd:2 -> left used {1,2}. Even positions: 2nd:5, 4th:4 -> right used {5,4}. So used numbers: 1,2,4,5. The remaining number is 3. Since there is one more number (the 5th), we will take the next left? Actually the pattern: After alternating, when L and R meet, we take that number. In this case after 4 numbers, L becomes 3, R becomes 3? Actually after using 4 numbers, the next left would be 3, and the next right would be 3 as well. So the last number (5th) is 3. So last = m+1? For m=2, m+1=3, correct. For k=2 (m=1): after 2 numbers, used: left {1}, right {3}. Remaining number is 2. So last=2 = m+1=2. So for even k, last = m+1 = k/2 + 1. That is >=2 for k>=2? For k=0 not allowed. So last >=2. For k even, last = k/2 + 1, which is >1.
For odd k: k=2m+1, then total numbers = k+1 = 2m+2 (even). We will have exactly m+1 left numbers? Actually alternating: we will use all numbers. Since even length, we will use m+1 left? Let's simulate: k=3 (m=1): numbers 1..4. Sequence: left:1, right:4, left:2, right:3. So left used {1,2}, right used {4,3}. All numbers used, last is right? Actually last (4th) is 3, which is the last right. For k=5 (m=2): numbers 1..6. Sequence: left:1, right:6, left:2, right:5, left:3, right:4. So left used {1,2,3}, right used {6,5,4}. Last (6th) is 4, which is the last right. So for odd k, last = (k+1)/2 + 1? For k=3: (3+1)/2+1 =2+1=3, correct. For k=5: (5+1)/2+1=3+1=4, correct. For k=1: (1+1)/2+1=1+1=2, correct. So last = (k+1)/2 + 1 = (k+3)/2? Actually (k+1)/2 + 1 = (k+3)/2. But note integer division: (k+1)/2 is floor? For odd k, (k+1)/2 is integer. So last = (k+3)/2. That's >=2 (for k=1 gives 2). So indeed last >=2.
Thus difference between last (which is at least 2) and next number (k+2) is at most (k+2 - 2) = k, and at least? Actually it's exactly (k+2 - last). Since last ≥ 2, diff ≤ k. Also diff could be as low as? If last is large, diff could be small. But it will be some number between 1 and k, which is already in our set (since we have all numbers 1..k from the prefix). So no new distinct difference is introduced.
Now, after we append the remaining numbers in increasing order, the differences among them are all 1 (since consecutive). So those differences are 1, which is already in the set. So overall, the set of differences is exactly {1,2,...,k}. However, we must check whether any difference appears that we didn't intend? The prefix uses differences from k down to 1. The transition from prefix to suffix gives a difference of some d between 1 and k (inclusive). The suffix internal differences are 1. So the union is subset of {1,...,k}. Since the prefix already includes all of 1..k, the set remains exactly {1,...,k}. Therefore, the construction works for any n and k with 1 ≤ k < n.
But wait: need to ensure that the transition difference is indeed ≤ k and also that it doesn't introduce a new value beyond the set, but as argued it's ≤ k. However, is it possible that the transition difference is exactly something not yet covered? It could be, but it's ≤ k, and the prefix already includes all numbers 1..k, so even if it is some d that was already present, it's fine. Actually we need to make sure that we have all k distinct values. The prefix ensures that all k values appear because the differences in the prefix are exactly 1,2,...,k (as shown). So the set already contains all k values. The later edges (transition and suffix) don't add new values, so the total distinct count remains k. Good.
Now, we must also consider the case when n = k+1 exactly. Then there are no remaining numbers after the prefix. Our permutation is just the prefix of length n (which is k+1). In that case, we have exactly k differences (since n-1 = k). The differences are 1..k, all distinct. So distinct count = k, which satisfies the requirement. Example: n=4, k=3 gives prefix 1,4,2,3 as above, differences 3,2,1 -> distinct 3. Works. n=2, k=1: prefix 1,2 -> difference 1 -> distinct 1. Works.
Also, for n > k+1, we append increasing numbers from k+2 to n. The transition difference: between the last element of prefix (call it L) and k+2. We need to ensure that L is not equal to k+2? That's fine because L is at most k+1, and k+2 is greater, so diff = (k+2 - L). Since L >= 2, diff <= k. Also need to check that we are not accidentally skipping any number or duplicating. We've used 1..k+1 in prefix, then we use k+2,...,n in increasing order, so all numbers used exactly once.
Thus the construction works for all n,k with 1 ≤ k < n.
But wait: what about k = n-1? Then we need n-1 distinct differences, which is the maximum possible. Our construction yields differences: the prefix of length k+1 = n uses all numbers 1..n-1 exactly once. But does our prefix of length n (since n = k+1) produce a permutation of 1..n with differences covering 1..n-1? Yes, as argued for n = k+1, the prefix is exactly the permutation of length n with differences covering 1..(n-1) all distinct. So that matches the requirement for maximum distinct differences. Example: n=5,k=4 yields permutation: 1,5,2,4,3? Let's check: differences: 4,3,2,1 -> distinct set {1,2,3,4}. That's valid. So maximum distinct.
Now check sample: n=5,k=2 gave 1,3,2,4,5 as we described. That matches sample.
So the construction seems correct.
But is there any edge case? For n=2, k=1: our method: prefix of length k+1=2 -> permutation 1,2 -> diff 1. Good.
For n=100000, k=1: prefix length 2 -> 1,2 then append 3..100000 in increasing order. Permutation: 1,2,3,4,...,100000. Differences all 1 -> distinct set {1}. That's valid.
For n=100000, k=99999: prefix length 100000 -> permutation built by alternating from ends of 1..100000. That will have differences from 99999 down to 1, all distinct. Good.
Thus the solution is straightforward: produce an array p of length n. First, create the first min(k+1, n) numbers? Actually always n≥k+1? Since k < n, k+1 ≤ n? Actually if k = n-1, then k+1 = n, okay. If k < n-1, then k+1 ≤ n-1? Actually k < n, so k+1 ≤ n. Yes because if k ≤ n-1, then k+1 ≤ n. So we always have at least k+1 numbers. So we can always take the first k+1 numbers arranged as described. Then append the rest (if any) in increasing order.
But caution: if n = k+1, then we should not append anything extra; just the prefix. If n > k+1, we append the numbers from k+2 to n in ascending order.
Implementation: We'll generate p as an empty list. We'll maintain two pointers: left = 1, right = k+1. We'll alternate adding left then right, increment left, decrement right, until we have placed k+1 numbers. However, careful: The alternating should continue until we have placed all numbers from 1 to k+1. There are k+1 numbers. We can do a for i in range(1, k+2) (since we need k+1 numbers). For each i, if i is odd, take from left and increment left; if i is even, take from right and decrement right. But we must ensure we don't double count when left > right? Actually the process will naturally stop when we have placed k+1 numbers because we will have exactly taken all numbers. But if we implement a while loop with condition left <= right, we would generate only up to when they meet, but for even length (k+1 even) the loop would stop after placing left==right? Let's test: For k+1=4 (k=3), left=1, right=4. Iteration 1: add left=1, left=2; then add right=4, right=3; now left=2, right=3; left<=right true; add left=2, left=3; then add right=3, right=2; now left=3, right=2, loop stops. We have added 4 numbers: 1,4,2,3. That's correct. So while left <= right works: each iteration we add left then right? But careful: In the while loop, if we add left then check condition again and then add right, we may add an extra if not careful. Better to use a for loop over i from 0 to k (0-index) and decide based on parity.
Simpler: We can generate the first k+1 numbers as: p = [0]*n index = 0 l = 1 r = k+1 flag = True # start with left while l <= r: if flag: p[index] = l l += 1 else: p[index] = r r -= 1 index += 1 flag = not flag But this will generate only up to when l>r, but that yields exactly k+1 numbers? Let's test: for k+1=4: l=1,r=4, flag=True initially. Iter1: add l=1, l=2, index=1, flag=False. Iter2: add r=4, r=3, index=2, flag=True. Iter3: l=2 <= r=3, flag=True: add l=2, l=3, index=3, flag=False. Iter4: l=3 <= r=3, flag=False: add r=3, r=2, index=4, flag=True. Now l=3, r=2, loop exits. We have added 4 numbers: 1,4,2,3. Works. For odd length: k+1=5 (k=4): l=1,r=5. Iter1: add 1, l=2, flag=F. Iter2: add 5, r=4, flag=T. Iter3: add 2, l=3, flag=F. Iter4: add 4, r=3, flag=T. Iter5: l=3 <= r=3, flag=T: add 3, l=4, flag=F. Now l=4, r=3, exit. Added 5 numbers: 1,5,2,4,3. Works. So while l<=r works and yields exactly k+1 numbers. Good.
After that, we have index = k+1. Then for i from k+2 to n, we set p[index] = i and index++. This will fill the rest in increasing order.
We need to output the permutation. Check that the transition difference between p[k] (last of prefix) and p[k+1] (first of suffix) is indeed ≤ k. As argued, p[k] (since zero-indexed, careful: prefix length = k+1, so indices 0..k. The last prefix element is at index k. The first suffix element is k+2 (since we start from k+2). So we need to compute diff = (k+2) - p[k]. p[k] is the last element from prefix. For even k, p[k] = k/2 +1. For odd k, p[k] = (k+3)/2. Let's compute diff for both:
- If k even: k=2m. Then p[k] = m+1. Diff = (2m+2) - (m+1) = m+1 = k/2 +1. Since k/2+1 ≤ k? For k≥2, k/2+1 ≤ k? For k=2, 2/2+1=2 ≤2 true. For k=4, 2+1=3 ≤4 true. So diff ≤ k. And diff is some number, but already present.
- If k odd: k=2m+1. Then p[k] = (k+3)/2 = (2m+1+3)/2 = (2m+4)/2 = m+2. Diff = (k+2) - (m+2) = (2m+1+2) - (m+2) = (2m+3) - (m+2) = m+1. Which is ≤ k? m+1 ≤ 2m+1 for m≥0, yes. So diff ≤ k.
Thus fine.
Now, check that all differences are indeed within 1..k. Also note that in the suffix we have consecutive numbers, so differences of 1. Those are okay.
Therefore this construction satisfies the problem.
But wait: What about the case where k=0? Not allowed because k < n and k ≥ 1? Input says positive integers n,k (1 ≤ k < n ≤ 10^5). So k ≥ 1.
Thus solution is simple.
But is there any scenario where the prefix length (k+1) is > n? That cannot happen because k < n, so k+1 ≤ n? Actually if k=n-1, then k+1=n, equals n. If k=n? Not allowed because k < n. So k+1 ≤ n always. Good.
Now we need to output the permutation. Let's verify with given examples.
Example1: n=3,k=2. Construct: prefix length 3 (k+1=3). left=1,right=3. Sequence: add 1, then 3, then? l=1->add1 ->l=2; flag=F->add r=3 -> r=2; flag=T-> l=2 <= r=2 so add l=2 -> l=3; loop exit. So p = [1,3,2]. Then suffix none (since n=3). Output matches.
Example2: n=3,k=1. prefix length 2: left=1,right=2. Sequence: add1 (l=2), flag=F; add2 (r=1), exit. p=[1,2]. Then suffix: from i=3 to 3 -> add 3. So p=[1,2,3]. Output matches.
Example3: n=5,k=2. prefix length 3: [1,3,2]. Then suffix: i=4,5 => [1,3,2,4,5]. Output matches.
Thus correct.
Now we should ensure that for larger n and k, the construction yields exactly k distinct differences and that it's a permutation.
Potential pitfalls: The construction uses numbers up to n. After prefix we append numbers from k+2 to n. But what if k+2 > n? That is when n = k+1, then we don't append anything. So fine.
Now complexity O(n). Memory O(n) or we can output directly.
Now, is there any case where the set of differences becomes less than k because some difference from 1..k is not actually used? In prefix, we claimed the differences are exactly 1..k. Let's verify for all k. The differences in the prefix are as derived: for i from 1 to k, d_i = |p_i - p_{i+1}|. We argued that the set is {1,2,...,k}. But is it always exactly all of them? Let's check for k=1: prefix length 2: p1=1,p2=2 => d1=1 -> set {1}. Good.
For k=2: prefix 1,3,2: differences: 2,1 -> set {1,2}. Good.
For k=3: 1,4,2,3: differences: 3,2,1 -> set {1,2,3}. Good.
For k=4: 1,5,2,4,3: differences: 4,3,2,1 -> set {1,2,3,4}. Good.
For k=5: 1,6,2,5,3,4: differences: 5,4,3,2,1 -> good.
So indeed, the prefix's differences are all distinct and cover 1..k. This can be proven: The differences are k, k-1, k-2, ..., 1 in that order. So the set size is k.
Now, after we append the suffix, we might get some additional differences: the transition difference and the 1's. But those are within 1..k, so they don't add new distinct values. However, we must ensure that the transition difference does not accidentally equal something that was missing? It doesn't matter because all are already present. So total distinct remains k.
Thus solution is correct.
Now, we should also consider if there is any possibility that the transition difference is 0? That would happen if the last prefix number equals k+2, which cannot because last prefix is at most k+1. So no.
Thus implementation: read n, k. Then create an array p of size n. Use two pointers l=1, r=k+1. Use a boolean flag = True. idx=0. While l <= r: if flag: p[idx]=l; l++; else: p[idx]=r; r--; idx++; flag = !flag. This will fill first k+1 elements. Then for i from k+2 to n: p[idx]=i; idx++. Print p.
But careful: The while loop condition l <= r will produce exactly k+1 numbers. However, we should ensure that we have exactly k+1 numbers. Let's test with k+1=2: l=1,r=2, flag initially True. Iter1: flag True -> p[0]=1; l=2; flag=False; idx=1. Now l=2 <= r=2 -> loop continues. Iter2: flag False -> p[1]=2; r=1; flag=True; idx=2. Now l=2, r=1, exit. So we have 2 numbers, correct. So loop works.
Now complexity O(n). That's fine.
But is there any possibility that the while loop might produce fewer than k+1 numbers if we start with flag False? But we start with flag True to get left first. Starting with True is important? Let's see: If we start with False, we would get right first. Would that also work? Possibly, but the order might be different, but still the differences would be k,...,1? Let's test k=2 start with right: sequence: 3,1,2? Actually l=1,r=3, flag False initially. Then add r=3, r=2, flag True; then add l=1, l=2, flag False; then l=2 <= r=2, flag False? Wait after second addition, flag becomes False? Let's simulate: start flag=False. Iter1: add r=3, r=2, flag=True, idx=1. Iter2: l=1 <= r=2, flag=True -> add l=1, l=2, flag=False, idx=2. Iter3: l=2 <= r=2, flag=False -> add r=2, r=1, flag=True, idx=3. Now we have [3,1,2]. Differences: 2,1 -> set {1,2}. That's also fine. But does the transition difference after suffix change? The last prefix would be 2, same as before. So it works as well. But careful: For k=3 starting with right: l=1,r=4, flag=False: sequence: 4,1,3,2? Actually: Iter1: add r=4, r=3, flag=True Iter2: l=1<=3, add 1, l=2, flag=False Iter3: l=2<=3, flag=False? Wait flag now False, so add r=3, r=2, flag=True Iter4: l=2<=2, flag=True, add l=2, l=3, flag=False, exit. So sequence: 4,1,3,2. Differences: 3,2,1 -> set {1,2,3}. Good. Last element is 2. Then transition to k+2=5 gives diff 3. So it's still ok. So either starting side works. But our initial construction described left first yields a specific pattern. Both are fine.
But we must ensure the prefix includes all numbers 1..k+1 exactly once. The alternating algorithm with l and r, regardless of starting side, will produce a permutation of those numbers. So we can just do that.
Now, one more check: The while loop condition l <= r works for both starting sides, as long as we flip flag each time. But careful: The number of iterations equals the number of numbers placed. Since we place one number per iteration, and we stop when l > r. For even length, after placing the last number, l and r will cross exactly, and we'll have placed all numbers. For odd length, after placing the last number, l becomes > r, but we placed the number when l==r, then we increment either l or r causing crossing. So we have placed all numbers. So it's fine.
Thus the algorithm is correct.
But we need to verify that the suffix addition of increasing numbers doesn't cause any duplicate numbers. Since we used 1..k+1 in prefix, and then use k+2..n, all distinct.
Now, potential corner case: n=1? But constraints: n≥2 because k<n and k≥1, so n≥2. So fine.
Now, also need to consider that k may be as large as n-1, then we have no suffix. The while loop will produce all n numbers. So we output exactly that.
Thus the solution is straightforward.
But wait: Are we certain that the prefix's differences are exactly 1..k? Let's double-check for k even and odd. Already tested. So set size from prefix alone is k. Later differences don't introduce new ones, so total distinct is exactly k.
Now, let's test some random values with code mentally.
Case n=10,k=5. Prefix length 6: l=1,r=6. With left-first: sequence: 1,6,2,5,3,4. Differences: 5,4,3,2,1. Then suffix: 7,8,9,10. Transition: last prefix=4, first suffix=7, diff=3. So differences: 5,4,3,2,1,3,1,1,1 -> distinct {1,2,3,4,5}. Good.
Case n=10,k=7. Prefix length 8: l=1,r=8. Sequence: left-first: 1,8,2,7,3,6,4,5. Differences: 7,6,5,4,3,2,1 (since 1-8=7,8-2=6,2-7=5,7-3=4,3-6=3,6-4=2,4-5=1). Then suffix: 9,10. Transition: last prefix=5, first suffix=9, diff=4 (which is in 1..7). Then suffix diff 1. Distinct remains {1..7}. Good.
Case n=6,k=1. Prefix length 2: 1,2. Suffix