How do I generate a "special sequence" quickly?

Given N (3 <= N <= 200), which is either a multiple of four or one less than a multiple of four, generate a "special sequence" of 2N numbers, in which each integer between 1 and N appears twice. Additionally, the two integers of k must be separated by k other numbers.

For example, if N = 3, a valid sequence would be 3 1 2 1 3 2, as the 3's are separated by three numbers 1 2 1, the 2's are separated by two numbers 1 3, and so on.

Using branch and bound, I can achieve N <= 80 in under one second with c++11. However, it seems the solution to this is by generating the sequence via some pattern... but I can not identify it.

Any help would be much appreciated.