```
class Solution {
public:
vector<int> constructArray(int n, int k) {
//use 1 to n to construct k
//
vector<int> ret;
//in order to make k diff, we need 1 and k + 1
//use 1 to 1 + k to make tail, tail only contribute diff 1, this will make sure in the future we will not add any different diff, so handle the tail first.
for(int i = k + 2; i <= n; ++i)
{
ret.push_back(i);
}
//now every high - low couple make a new diff
int low = 1;
int high = 1 + k;
while(low <= high)
{
if(low != high)
{
ret.insert(ret.begin(), high);
ret.insert(ret.begin(), low);
--high;
++low;
}
else
{
ret.insert(ret.begin(), high);
++low;
--high;
}
}
return ret;
}
};
```