using System.Linq;

​

using static System.Array;

​

public class ArrayUtils{

    public static void Shuffle<T>(T[] a) {

        for(int i=1,l=-~a.Length/2;i<l;){Reverse(a,2*i-1,l-i+1);Reverse(a,2*i++,l-i+1);}

    }

​

    public static void Main() {

        void Assert(int[] a, int[] expected) {

            Shuffle(a);

            if (!a.SequenceEqual(expected)) 

                throw new System.Exception($"Expected [{string.Join(", ", expected)}], got [{string.Join(", ", a)}]");

        }

        int[] Build(int m) {

            int[] test = new int[m];

            for(int i = 0; i < (m%2==0? m/2 : m/2+1); i++) test[2*i] = i;

            for(int i = m%2==0? m/2 : m/2+1; i < m; i++) test[2*(i-m/2)+(m%2==0?1:-1)] = i;

            return test;

        }

        Assert(new int[0], new int[0]);

        Assert(new int[]{0}, new int[1]{0});

        Assert(new int[]{0,1}, new int[]{0,1});

        Assert(new int[]{0,1,2}, new int[]{0,2,1});

        Assert(new int[]{1,2,3,4}, new int[]{1,3,2,4});

        Assert(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0}, new int[]{1, 6, 2, 7, 3, 8, 4, 9, 5, 0});

        Assert(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1}, new int[]{1, 7, 2, 8, 3, 9, 4, 0, 5, -1, 6});

        //Assert(Enumerable.Range(0, 1<<20).ToArray(), Build(1<<20));

        //Assert(Enumerable.Range(0, 1+1<<18).ToArray(), Build(1+1<<18));

        for(int i = 5; i < 400; i++) Assert(Enumerable.Range(0, i).ToArray(), Build(i));

        System.Console.WriteLine("All tests passed.");

    }

}