using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Chalenge
{
    class Program
    {
        public static void RollMinMax(int[] arr)
        {
            Console.WriteLine(new String('-', 45));
            Console.WriteLine("before: [{0}]", string.Join(", ", arr));

            int min = 0, max = 0, tmp, offset = 1;
            bool maxInPlace = false, minInPlace = false;
            int N = arr.Length;

            for (int i = 0; i < N; i++)
            {
                if (i < N / 2)
                {
                    if (arr[min] > arr[N - 1 - i])
                        min = N - 1 - i;
                    if (arr[min] > arr[i])
                        min = i;
                    if (arr[max] < arr[i])
                        max = i;
                    if (arr[max] < arr[N - 1 - i])
                        max = N - 1 - i;
                }
                else
                {
                    if (i == N / 2 && max > min)
                    {   // only once. locate max left to min
                        Switch(arr, min, max);
                        tmp = min;
                        min = max;
                        max = tmp;
                    }

                    if (max - offset >= 0)
                        Switch(arr, max - offset + 1, max - offset);
                    else
                        maxInPlace = true;

                    if (min + offset <= N - 1)
                        Switch(arr, min + offset - 1, min + offset);
                    else
                        minInPlace = true;

                    offset += 1;

                    // if min or max in place then do another shift to the other
                    if (maxInPlace && min + offset <= N - 1)
                    {
                        Switch(arr, min + offset - 1, min + offset);
                        offset += 1;
                    }
                    else if (minInPlace && max - offset >= 0)
                    {
                        Switch(arr, max - offset + 1, max - offset);
                        offset += 1;
                    }
                }
            }
            Console.WriteLine("after : [{0}]", string.Join(", ", arr));
        }

        public static void Switch(int[] arr, int index1, int index2)
        {
            int tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }

        static void Main(string[] args)
        {
            int[] arr1 = { 2, 4, 56, 6, 7, 45, 23, 9, 1, 8, 10, 3 };
            int[] arr1exp = { 56, 2, 4, 6, 7, 45, 23, 9, 8, 10, 3, 1 };
            RollMinMax(arr1);
            if (!arr1.SequenceEqual(arr1exp))
                Console.WriteLine("TEST FAILED 1");

            int[] arr2 = { 2, 4, 56, 6, 7, 45, 23, 9, 1, 8, 10 };
            int[] arr2exp = { 56, 2, 4, 6, 7, 45, 23, 9, 8, 10, 1 };
            RollMinMax(arr2);
            if (!arr2.SequenceEqual(arr2exp))
                Console.WriteLine("TEST FAILED 2");

            int[] arr3 = { 56, 4, 2, 6, 7, 45, 23, 9, 10, 8, 1 };
            int[] arr3exp = { 56, 4, 2, 6, 7, 45, 23, 9, 10, 8, 1 };
            RollMinMax(arr3);
            if (!arr3.SequenceEqual(arr3exp))
                Console.WriteLine("TEST FAILED 3");

            int[] arr4 = { 4, 2, 6, 7, 45, 23, 9, 10, 8, 1, 56 };
            int[] arr4exp = { 56, 4, 2, 6, 7, 45, 23, 9, 10, 8, 1 };
            RollMinMax(arr4);
            if (!arr4.SequenceEqual(arr4exp))
                Console.WriteLine("TEST FAILED 4");

            int[] arr5 = { 1, 56, 6, 7, 45, 23, 9, 10, 8, 4, 2 };
            int[] arr5exp = { 56, 6, 7, 45, 23, 9, 10, 8, 4, 2, 1 };
            RollMinMax(arr5);
            if (!arr5.SequenceEqual(arr5exp))
                Console.WriteLine("TEST FAILED 5");

            int[] arr6 = { 2, 4, 1, 6, 7, 45, 23, 9, 56, 8, 10 };
            int[] arr6exp = { 56, 2, 4, 6, 7, 45, 23, 9, 8, 10, 1 };
            RollMinMax(arr6);
            if (!arr6.SequenceEqual(arr6exp))
                Console.WriteLine("TEST FAILED 6");

            int[] arr7 = { 2, 4, 1, 6, 7, 45, 11, 23, 9, 56, 8, 10 };
            int[] arr7exp = { 56, 2, 4, 6, 7, 45, 11, 23, 9, 8, 10, 1 };
            RollMinMax(arr7);
            if (!arr7.SequenceEqual(arr7exp))
                Console.WriteLine("TEST FAILED 7");

            // max, min at end
            int[] a31 = { 14, 13, 9, 9, 20, 12, 4, 6, 37, 1, 9, 25 };
            int[] a31exp = { 37, 14, 13, 9, 9, 20, 12, 4, 6, 9, 25, 1 };
            RollMinMax(a31);
            if (!a31.SequenceEqual(a31exp))
                Console.WriteLine("TEST FAILED\n");

            // max, min at end
            int[] a43 = { 14, 13, 9, 9, 20, 12, 4, 6, 9, 25, 37, 1 };
            int[] a43exp = { 37, 14, 13, 9, 9, 20, 12, 4, 6, 9, 25, 1 };
            RollMinMax(a43);
            if (!a43.SequenceEqual(a43exp))
                Console.WriteLine("TEST FAILED\n");

            // min, max at end
            int[] a42 = { 3, 34, 9, 9, 20, 12, 4, 6, 9, 25, 1, 37 };
            int[] a42exp = { 37, 3, 34, 9, 9, 20, 12, 4, 6, 9, 25, 1 };
            RollMinMax(a42);
            if (!a42.SequenceEqual(a42exp))
                Console.WriteLine("TEST FAILED");

            int[] a41 = { 3, 34, 9, 9, 20, 12, 1, 6, 9, 25, 10, 37 };
            int[] a41exp = { 37, 3, 34, 9, 9, 20, 12, 6, 9, 25, 10, 1 };
            RollMinMax(a41);
            if (!a41.SequenceEqual(a41exp))
                Console.WriteLine("TEST FAILED");

            // max, min at begining
            int[] a51 = { 34, 3, 9, 9, 20, 12, 4, 6, 9, 25, 7, 7 };
            int[] a51exp = { 34, 9, 9, 20, 12, 4, 6, 9, 25, 7, 7, 3 };
            RollMinMax(a51);
            if (!a51.SequenceEqual(a51exp))
                Console.WriteLine("TEST FAILED\n");

            // min, max at begining
            int[] a2 = { 3, 34, 9, 9, 20, 12, 4, 6, 9, 25, 7, 7 };
            int[] a2exp = { 34, 9, 9, 20, 12, 4, 6, 9, 25, 7, 7, 3 };
            RollMinMax(a2);
            if (!a2.SequenceEqual(a2exp))
                Console.WriteLine("TEST FAILED\n");

            // max, min at middle
            int[] a5 = { 3, 34, 9, 9, 20, 42, 1, 6, 9, 25, 2, 37 };
            int[] a5exp = { 42, 3, 34, 9, 9, 20, 6, 9, 25, 2, 37, 1 };
            RollMinMax(a5);
            if (!a5.SequenceEqual(a5exp))
                Console.WriteLine("TEST FAILED");

            // min, max at middle
            int[] a6 = { 3, 34, 9, 9, 20, 1, 42, 6, 9, 25, 2, 37 };
            int[] a6exp = { 42, 3, 34, 9, 9, 20, 6, 9, 25, 2, 37, 1 };
            RollMinMax(a6);
            if (!a6.SequenceEqual(a6exp))
                Console.WriteLine("TEST FAILED");

            int[] a7 = { 16, 12, 19, 19, 13, 17, 11, 1, 100 };
            int[] a7exp = { 100, 16, 12, 19, 19, 13, 17, 11, 1 };
            RollMinMax(a7);
            if (!a7.SequenceEqual(a7exp))
                Console.WriteLine("TEST FAILED");

            Console.ReadLine();
        }
    }
}