Max's Anger Contest Series 1 P3 - Divide and Connor

View as PDF

Submit solution


Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

To test his divide and conquer abilities, Max decided to try a new technique of splitting his array, A, of N integers into 3 equally-sized segments and reassembling them in a new order:

  • If the current segment is 1 element, return it.
  • Otherwise, split the current segment into 3 segments and apply the technique again on each segment. After applying the technique again, he will take the first segment and move it to the second segment's position, the second segment and move it to the third segment's position, and finally, the third segment and move it to the first segment's position. Finally, return this new segment.

If A = [1, 2, 3, 4, 5, 6, 7, 8, 9], he will split it into 3 segments: [[1, 2, 3], [4, 5, 6], [7, 8, 9]].

Then, he will split each segment again: [[[1], [2], [3]], [[4], [5], [6]], [[7], [8], [9]]].

Now, merge each segment based on those rules: [[3, 1, 2], [6, 4, 5], [9, 7, 8]].

Finally, merge once more and get the final array: [9, 7, 8, 3, 1, 2, 6, 4, 5].

Can you find the final array after applying this technique?

Constraints

1 \le N \le 3^{11}

N will be a power of 3.

1 \le A_i \le 10^9

Input Specification

The first line will contain an integer, N, the number of array elements.

The second line will contain N integers, A_i, the elements of the array.

Output Specification

Output the array after applying this technique.

Sample Input

9
1 2 3 4 5 6 7 8 9

Sample Output

9 7 8 3 1 2 6 4 5

Comments

There are no comments at the moment.