#30daysofcode #day20

// https://www.hackerrank.com/challenges/30-sorting/

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());
        string[] a_temp = Console.ReadLine().Split(' ');
        int[] a = Array.ConvertAll(a_temp,Int32.Parse);

        // Write Your Code Here
        int numSwaps = 0;
        for (int i = 0; i < n; i++) {
            // Track number of elements swapped during a single array traversal
            int numberOfSwaps = 0;

            for (int j = 0; j < n - 1; j++) {
                // Swap adjacent elements if they are in decreasing order
                if (a[j] > a[j + 1]) {
                    //swap(a[j], a[j + 1]);
                    int seged = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = seged;
                    numberOfSwaps++;
                }
            }
            numSwaps += numberOfSwaps;
            // If no elements were swapped during a traversal, array is sorted
            if (numberOfSwaps == 0) {
                break;
            }
        }

        Console.WriteLine("Array is sorted in {0} swaps.", numSwaps);
        Console.WriteLine("First Element: " + a[0]);
        Console.WriteLine("Last Element: " + a[n-1]);
    }
}