#include <iostream>
using namespace std;
 
int main() {
    int arr[] = {2, 3, 4, 1, 9, 5, 1, 2, 6, 8, 1, 3};
    int arrLength = 12;
    for (int i = 0; i < arrLength; i++)
    {
       int minPos = -1;
       for (int j = i; j < arrLength; j++)
          // either it's the first element, or it's greater than the last element
          //   and either it's the first such element we find, or smaller than the best one
          if ((i == 0 || arr[j] > arr[i-1]) && 
              (minPos == -1 || arr[j] < arr[minPos]))
          {
             minPos = j;
          }
 
       // no more elements to sort
       if (minPos == -1)
          break;
 
       int temp = arr[i];
       arr[i] = arr[minPos];
       arr[minPos] = temp;
    }
    for (int i = 0; i < arrLength; i++)
       cout << arr[i] << " ";
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CiAgICBpbnQgYXJyW10gPSB7MiwgMywgNCwgMSwgOSwgNSwgMSwgMiwgNiwgOCwgMSwgM307CiAgICBpbnQgYXJyTGVuZ3RoID0gMTI7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGFyckxlbmd0aDsgaSsrKQogICAgewogICAgICAgaW50IG1pblBvcyA9IC0xOwogICAgICAgZm9yIChpbnQgaiA9IGk7IGogPCBhcnJMZW5ndGg7IGorKykKICAgICAgICAgIC8vIGVpdGhlciBpdCdzIHRoZSBmaXJzdCBlbGVtZW50LCBvciBpdCdzIGdyZWF0ZXIgdGhhbiB0aGUgbGFzdCBlbGVtZW50CiAgICAgICAgICAvLyAgIGFuZCBlaXRoZXIgaXQncyB0aGUgZmlyc3Qgc3VjaCBlbGVtZW50IHdlIGZpbmQsIG9yIHNtYWxsZXIgdGhhbiB0aGUgYmVzdCBvbmUKICAgICAgICAgIGlmICgoaSA9PSAwIHx8IGFycltqXSA+IGFycltpLTFdKSAmJiAKICAgICAgICAgICAgICAobWluUG9zID09IC0xIHx8IGFycltqXSA8IGFyclttaW5Qb3NdKSkKICAgICAgICAgIHsKICAgICAgICAgICAgIG1pblBvcyA9IGo7CiAgICAgICAgICB9CgogICAgICAgLy8gbm8gbW9yZSBlbGVtZW50cyB0byBzb3J0CiAgICAgICBpZiAobWluUG9zID09IC0xKQogICAgICAgICAgYnJlYWs7CgogICAgICAgaW50IHRlbXAgPSBhcnJbaV07CiAgICAgICBhcnJbaV0gPSBhcnJbbWluUG9zXTsKICAgICAgIGFyclttaW5Qb3NdID0gdGVtcDsKICAgIH0KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYXJyTGVuZ3RoOyBpKyspCiAgICAgICBjb3V0IDw8IGFycltpXSA8PCAiICI7CglyZXR1cm4gMDsKfQ==