Subtask 1

Note that it is not possible for there to be only one distinct difference since $1$ is not prime. Thus we can conjecture that the smallest possible number of distinct differences is $2$. Let's try to build a permutation that uses only the differences $2$ and $-3$. One way of doing this is to repeat the pattern $1,3,5,2,4,6,8,10,7,9,\dots$ (repeating the differences $2,2,-3,2,2$ periodically) which works whenever $N$ is a multiple of $5$.

Time Complexity: $\mathcal{O}(N)$ for each test case.

Subtask 2

From here on, we will use 0-indexing for all indices and values of $p_i$ as that will turn out to be more convenient.

Again, we can conjecture that the smallest possible number of distinct differences is $2$ for all $N$ that is not too small.

Let's find two distinct prime numbers $p$ and $q$ with $p+q=N$. By Goldbach's conjecture, we expect that such $p$ and $q$ will exist whenever $N$ is even and not too small. Goldbach's conjecture is unproven and doesn't guarantee that the two primes are distinct, but it is possible to verify using a computer that such $p\ne q$ exists for all even $N$ between $8$ and ${10}^6$. Cases where $N$ is small ($N=2,4,6$) may need to be handled separately, and we can find an answer for these small $N$ by hand and hardcode them.

Now consider setting $p_i=(i\cdot pmodN)$ for all $0\le i\le N-1$. We have that $p_{i+1}\equiv p_i+p(\mathrm{mod}N)$, so either $p_{i+1}=p_i+p$ (if $p_i+p<N$) or $p_{i+1}=p_i+p-N=p_i-q$ (if $p_i+p\ge N$) for all $0\le i\le N-2$. Hence this sequence only has two distinct adjacent differences ($p$ and $-q$) as needed. Furthermore, this is a permutation since $gcd(p,N)=gcd(p,p+q)=gcd(p,q)=1$ (because $p$ and $q$ are distinct primes), and this means that if $p_i=p_j$, then $p_i-p_j\equiv (i-j)p\equiv 0(\mathrm{mod}N)⟹i-j\equiv 0(\mathrm{mod}N)⟹i=j$.

If we implement this solution by sieving all the primes up to $N$, then the time complexity is $\mathcal{O}(N\log \log N)$. It is also possible to obtain $\mathcal{O}(N)$ behaviour by trying $p$ in increasing order and checking if $p$ and $q=N-p$ are both prime (in $\mathcal{O}(\sqrt{N})$ time for each $p$), as we will intuitively find a good $p$ and $q$ way before checking $\mathcal{O}(\sqrt{N})$ numbers.

Time Complexity: $\mathcal{O}(N\log \log N)$ (or $\mathcal{O}(N)$ behaviour) for each test case.

Subtask 3

First, we handle the small $N$ separately, which now includes all $N$ between $1$ and $7$.

If $N$ is even, we can do the construction as in subtask 2. Note that the above construction in fact gives a cyclic sequence with only $p$ and $-q$ as adjacent differences ($p_0-p_{N-1}=p$ or $-q$ as well). Thus if $N$ is odd, we can perform the above construction for $N-1$ to obtain a permutation $p_0,p_1,\dots ,p_{N-2}$ of $0,1,\dots ,N-2$, cyclically shift it so that $p_{N-2}=N-p-1$, and set $p_{N-1}=N-1$ (in fact, if we use the exact same formula as shown above, we do not even need to do a cyclic shift as $p_{N-2}\equiv (N-2)p\equiv -p\equiv q(\mathrm{mod}N-1)⟹p_{N-2}=q=N-p-1$).

Time Complexity: $\mathcal{O}(N\log \log N)$ (or $\mathcal{O}(N)$ behaviour) for each test case.

Remark: The properties of the prime numbers this problem uses are:

• Goldbach's conjecture, allowing us to find primes $p$ and $q$ with $p+q=N$ or $p+q=N-1$.
• Coprimeness of distinct primes, allowing the sequence $i\cdot pmodN$ to "cover" all residues modulo $N$.