Given two integers n and k, construct a list answer that contains n different positive integers ranging from 1 to n and obeys the following requirement:


	Suppose this list is answer =&nbsp;[a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.


Return the list answer. If there multiple valid answers, return any of them.

&nbsp;
Example 1:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1


Example 2:

Input: n = 3, k = 2
Output: [1,3,2]
Explanation: The [1,3,2] has three different positive integers ranging from 1 to 3, and the [2,1] has exactly 2 distinct integers: 1 and 2.


&nbsp;
Constraints:


	1 &lt;= k &lt; n &lt;= 104


class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        # n = 8, k = 5
        # 1 2 3 8 4 7 5 6
        # 1 1 5 4 3 2 1
        res = list(range(1,n-k+1))
        sign, val = 1, k
        for i in range(k):
            res.append(res[-1]+sign*val)
            sign *= -1
            val -= 1
        return res
class Solution {
    public int[] constructArray(int n, int k) {
        int [] result = new int[n];
        result[0] = 1;
        int sign = 1;
        for(int i = 1 ; i < n; i++, k--){
            if(k > 0){
                result[i] = result[i-1] + k * sign;
                sign *= -1;
            }
            else{
                result[i] = i+1;
            }
        }
        return result;
    }
}
class Solution {
public:
    vector<int> constructArray(int n, int k) {
        int diff = n - k;
        int lo = 1;
        int hi = n;
        vector<int> out;
        int i = 0; 
		// we generate a difference of 1 between subsequent elements for the first n-k times.
        while(i < diff){
            out.push_back(lo);
            lo++;
            i++;
        }
        bool flag = true;
		//Now we go zig zag to generate k unique differences, the last one will be automatically taken care
		//as the difference between last two elements will be one which we have already generated above.
        for(int i = out.size()   ; i < n ; i++){
           //flag to alternatively zig zag
		   if(flag){
                out.push_back(hi);
                hi--;
                flag = false;
            }
            else{
                out.push_back(lo);
                lo++;
                flag = true;
            }
        }
        return out;
    }
};
var constructArray = function(n, k) {
    const result = [];
    let left = 1;
    let right = n;

    for (let index = 0; index < n; index++) {
        if (k === 1) {
            result.push(left++);
            continue;
        }
        const num = k & 1 ? left++ : right--;
        result.push(num);
        k -= 1;
    }

    return result;
};
Beautiful Arrangement II