A Simple Sequence

Key Observation

The condition asks for the sequence

$$a_1 \bmod a_2,\ a_2 \bmod a_3,\ \ldots,\ a_{n-1}\bmod a_n$$

to be non-increasing. So we want remainders that are easy to control.

Here is the tiny trick: for every integer $x>1$,

$$x \bmod (x-1)=1.$$

That means consecutive decreasing numbers are perfect. They give remainder $1$ again and again.

Construction

Print the permutation in descending order:

$$[n,n-1,n-2,\ldots,2,1].$$

Now look at the remainders:

$$n\bmod(n-1)=1,$$ $$(n-1)\bmod(n-2)=1,$$

and so on, until

$$3\bmod2=1,$$

then finally

$$2\bmod1=0.$$

So the full remainder sequence is

$$1,1,1,\ldots,1,0.$$

And yes, that is non-increasing:

$$1\ge 1\ge \cdots \ge 1\ge 0.$$

That's it. The problem looks like it wants clever construction voodoo, but descending order just punches it in the face.

Correctness Proof

We output $a_i=n-i+1$, so the array is exactly the numbers from $1$ to $n$ in reverse order. Therefore it is a valid permutation.

For every adjacent pair except the last one, the pair has the form $(x,x-1)$ with $x\ge 3$. Hence

$$x\bmod(x-1)=1.$$

For the final adjacent pair $(2,1)$, we have

$$2\bmod1=0.$$

Thus the sequence of remainders is

$$1,1,\ldots,1,0,$$

which satisfies

$$1\ge1\ge\cdots\ge1\ge0.$$

So the required condition always holds.

Complexity

For each test case, we print $n$ numbers.

$$\text{Time Complexity}=O(n)$$ $$\text{Memory Complexity}=O(1)$$