Two elements can be swapped exactly when their values have the same remainder modulo , where the remainder is taken in \{0, 1, 2\}. Split the positions into three classes by a_i \bmod 3. The values never change, and a swap involves two positions of one class, so every class keeps its own multiset of values on its own positions.
Conversely, any two elements of one class may be swapped directly, and every permutation is a product of transpositions. Hence the values of a class can be arranged on the positions of that class in any order, independently of the other classes. The reachable arrays are exactly the arrays in which every class holds its own values in some order.
Let be the array in which every class receives its values sorted in increasing order, placed on its positions from left to right. It is the lexicographically smallest reachable array: take any other reachable array and the first position where b_i \ne c_i, and let be the class of . The positions of class to the left of hold the same values in and in , so c_i is one of the remaining values of class , and b_i is the smallest of them. Thus b_i < c_i.
So we collect the positions and the values of every class, sort the values and write them back in order. The only trap is the remainder of a negative number: in C++ and Java -1 \,\%\, 3 = -1, although 2 - (-1) = 3 is divisible by , so use ((a_i \,\%\, 3) + 3) \,\%\, 3.
The complexity is O(n \log n) per test case.