using System;

using System.Collections.Generic;

public class Program

{

    /*In an array of integers, a "peak" is an element which is greater than or equal to

    the adjacent integers and a "valley" is an element which is less than or equal to the adjacent integers.

    For example, in the array {5, 8, 6, 2, 3, 4, 6}, {8, 6} are peaks and {5, 2} are valleys. Given an array

    of integers, sort the array into an alternating sequence of peaks and valleys.*/

    //Input: {5, 3, 1, 2, 3}

    //Output: {5, 1, 3, 2, 3}

    private static void Swap(int[] arr, int i, int j){

        var temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

    public static void PeaksAndValleys(int[] arr){

        if (arr == null || arr.Length < 3){

            return;

        }

        for (var i=1; i<arr.Length-1; i+=2){

            if (arr[i] > arr[i-1] && arr[i] > arr[i+1]) continue;

            var max = Math.Max(Math.Max(arr[i-1],arr[i]),arr[i+1]);

            if (arr[i-1] == max){

                Swap(arr,i,i-1);

            }

            else Swap(arr,i,i+1);

        }

    }

    public static void Main()

    {

        var arr = new int[5]{5,3,1,2,3};

        PeaksAndValleys(arr);

        foreach(var e in arr){

            Console.Write(e+" ");

        }

    }

}