#include <stdio.h>
#include <stdbool.h>
 
void print_arr(int* arr, int len) {
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
int naive_sort(int* arr, int len, bool debug) {
    int count = 0;
    int i = 0, end = len-1;
 
    while (i < end) {
        while (i < end && arr[i] <= arr[i+1]) i++;
 
        if (i < end) {
        	if (debug) {
                print_arr(arr, len);
                printf("swap: %d %d\n", arr[i], arr[i+1]);
                printf("count: %d\n", count+1);
                printf("------\n");
        	}
 
            int temp = arr[i+1];
            for (int j = i+1; j > 0; j--)
                arr[j] = arr[j-1];
            arr[0] = temp;
 
            i = 0;
            count++;
        }
    }
 
    return count;
}
 
int main() {
    int arr[] = { 5, 1, 1, 2, 4, 3 };
    int len = sizeof(arr) / sizeof(int);
 
    print_arr(arr, len);
    printf("------\n");
 
    int count = naive_sort(arr, len, true);
 
    print_arr(arr, len);    
    printf("%d\n", count);
 
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRib29sLmg+Cgp2b2lkIHByaW50X2FycihpbnQqIGFyciwgaW50IGxlbikgewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBsZW47IGkrKykKICAgICAgICBwcmludGYoIiVkICIsIGFycltpXSk7CiAgICBwcmludGYoIlxuIik7Cn0KCmludCBuYWl2ZV9zb3J0KGludCogYXJyLCBpbnQgbGVuLCBib29sIGRlYnVnKSB7CiAgICBpbnQgY291bnQgPSAwOwogICAgaW50IGkgPSAwLCBlbmQgPSBsZW4tMTsKICAgIAogICAgd2hpbGUgKGkgPCBlbmQpIHsKICAgICAgICB3aGlsZSAoaSA8IGVuZCAmJiBhcnJbaV0gPD0gYXJyW2krMV0pIGkrKzsKICAgICAgICAKICAgICAgICBpZiAoaSA8IGVuZCkgewogICAgICAgIAlpZiAoZGVidWcpIHsKICAgICAgICAgICAgICAgIHByaW50X2FycihhcnIsIGxlbik7CiAgICAgICAgICAgICAgICBwcmludGYoInN3YXA6ICVkICVkXG4iLCBhcnJbaV0sIGFycltpKzFdKTsKICAgICAgICAgICAgICAgIHByaW50ZigiY291bnQ6ICVkXG4iLCBjb3VudCsxKTsKICAgICAgICAgICAgICAgIHByaW50ZigiLS0tLS0tXG4iKTsKICAgICAgICAJfQogICAgICAgICAgICAKICAgICAgICAgICAgaW50IHRlbXAgPSBhcnJbaSsxXTsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGkrMTsgaiA+IDA7IGotLSkKICAgICAgICAgICAgICAgIGFycltqXSA9IGFycltqLTFdOwogICAgICAgICAgICBhcnJbMF0gPSB0ZW1wOwogICAgICAgICAgICAKICAgICAgICAgICAgaSA9IDA7CiAgICAgICAgICAgIGNvdW50Kys7CiAgICAgICAgfQogICAgfQogICAgCiAgICByZXR1cm4gY291bnQ7Cn0KCmludCBtYWluKCkgewogICAgaW50IGFycltdID0geyA1LCAxLCAxLCAyLCA0LCAzIH07CiAgICBpbnQgbGVuID0gc2l6ZW9mKGFycikgLyBzaXplb2YoaW50KTsKICAgIAogICAgcHJpbnRfYXJyKGFyciwgbGVuKTsKICAgIHByaW50ZigiLS0tLS0tXG4iKTsKCiAgICBpbnQgY291bnQgPSBuYWl2ZV9zb3J0KGFyciwgbGVuLCB0cnVlKTsKCiAgICBwcmludF9hcnIoYXJyLCBsZW4pOyAgICAKICAgIHByaW50ZigiJWRcbiIsIGNvdW50KTsKCn0K