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 p \bmod N)~ for all ~0 \le i \le N-1~. We have that ~p_{i+1} \equiv p_i+p \pmod 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 \pmod N \implies i-j \equiv 0 \pmod N \implies 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 \pmod{N-1} \implies 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 p \bmod N~ to "cover" all residues modulo ~N~.