#include <bits/stdc++.h>

using namespace std;

// Selection sort that works on a copy of the input vector
void selectionSort(vector<int> &array) {
    int n = static_cast<int>(array.size()); // Number of elements in the vector

    // Iterate over each position where the next smallest element should be placed
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i; // Assume the current position holds the minimum

        // Scan the unsorted portion [i+1 .. n-1] to find the true minimum element
        for (int j = i + 1; j < n; ++j) {
            if (array[j] < array[minIdx]) {
                minIdx = j; // Update index of the smallest value found so far
            }
        }

        // If a smaller element was found, swap it into position i
        if (minIdx != i) {
            swap(array[i], array[minIdx]); // Standard library swap exchanges the two values
        }
    }
}