#include <stdio.h>

void swap(int &x, int &y)
{
    int h = x;
    x = y;
    y = h;
}

class Permutations
{
public:
    Permutations(int val_n) : n(val_n), _more(true)
    {
        a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = i;
    }
    ~Permutations()
    {
        delete []a;
    }
    bool more() { return _more; }
    void next()
    {
        _more = false;
        for (int i = n-2; i >= 0; i--)
            if (a[i] < a[i+1])
            {
                _more = true;
                for (int j = n-1; j > i; j--)
                    if (a[j] > a[i])
                    {
                        swap(a[j], a[i]);
                        break;
                    }
                i++;
                for (int j = n-1; j > i; j--, i++)
                    swap(a[j], a[i]);
                break;
            }
    }
    int n;
    int *a;
private:
    bool _more;
};

void testSort(int n, bool (*before)(int x, int y), bool (*check)(int n, int *a, int *org_a))
{
    for (Permutations perms(n); perms.more(); perms.next())
    {
        int a[n];
        for (int i = 0; i < perms.n; i++)
            a[i] = perms.a[i];
        {
            for (int c = 1; c < n; c++)
              for (int i = 0; i < c; i++)
                if (before(a[c], a[i]))
                {
                  int e = c+1;
                  for (int b = c; i < b; b--)
                  {
                    bool pass = true;
                    for (int j = b; j < e; j++)
                      if (before(a[b-1], a[j]))
                      {
                        pass = false;
                        break;
                      }
                    if (pass)
                    {
                      for (int j = b; j < e; j++)
                        swap(a[j-1], a[j]);
                      e--;
                    }
                  }
                  break;
                }
        }
        
        for (int i = 0; i < n; i++)
            printf("%3d", perms.a[i]);
        printf(" -> ");
        for (int i = 0; i < n; i++)
            printf("%3d", a[i]);
        if (check != 0)
            printf("  %s", check(n, a, perms.a) ? "ok" : "FAIL");
        printf("\n");
    }
}


bool test1(int x, int y)
{
    return x == y-1;
}

bool check1(int n, int *a, int *a_org)
{
    for (int i = 0; i < n-1; i++)
        if (a[i] > a[i+1])
            return false;
    return true;
}

bool test2(int x, int y)
{
    return x == y-2;
}

bool check2(int n, int *a, int *a_org)
{
    int even = 0;
    int odd = 1;
    for (int i = 0; i < n; i++)
        if (a[i] % 2 == 0)
        {
            if (a[i] != even)
                return false;
            even += 2;
        }
        else
        {
            if (a[i] != odd)
                return false;
            odd += 2;
        }
    return true;
}

bool test3(int x, int y)
{
    return x%2 == 0 && x == y-2;
}

bool check3(int n, int *a, int *a_org)
{
    int even = 0;
    int i_odd = 0;
    while (i_odd < n && a_org[i_odd]%2 == 0)
        i_odd++;
    for (int i = 0; i < n; i++)
        if (a[i] % 2 == 0)
        {
            if (a[i] != even)
                return false;
            even += 2;
        }
        else
        {
            if (a[i] != a_org[i_odd])
                return false;
            i_odd++;
            while (i_odd < n && a_org[i_odd]%2 == 0)
                i_odd++;
        }
    return true;
}

bool test4(int x, int y)
{
    return x < y && (x == 4 || y == 4);
}

bool check4(int n, int *a, int *a_org)
{
    int i_lt4 = 0;
    for (int i = 0; i < 4; i++)
    {
        while (i_lt4 < n && a_org[i_lt4] >= 4)
            i_lt4++;
        if (a[i] != a_org[i_lt4])
            return false;
        i_lt4++;
    }
    if (a[4] != 4)
        return false;
    int i_gt4 = 0;
    for (int i = 5; i < n; i++)
    {
        while (i_gt4 < n && a_org[i_gt4] <= 4)
            i_gt4++;
        if (a[i] != a_org[i_gt4])
            return false;
        i_gt4++;
    }
    return true;
}

int index(int n, int *a, int v)
{
    for (int i = 0; i < n; i++)
        if (a[i] == v)
            return i;
    return -1;
}

#define BEFORE(X,Y) ((X) == x && (Y) == y)
#define CHECK_PAIR(X,Y) if (index(n,a,X) >= index(n,a,Y)) return false;

bool test5(int x, int y)
{
    return    BEFORE(0, 1)
           || BEFORE(1, 2)
           || BEFORE(2, 3)
           || BEFORE(3, 4)
           || BEFORE(1, 5)
           || BEFORE(5, 3)
           || BEFORE(5, 6)
           || BEFORE(6, 7)
           || BEFORE(7, 8)
           || BEFORE(4, 8);
}

bool check5(int n, int *a, int *a_org)
{
    CHECK_PAIR(0, 1)
    CHECK_PAIR(1, 2)
    CHECK_PAIR(2, 3)
    CHECK_PAIR(3, 4)
    CHECK_PAIR(1, 5)
    CHECK_PAIR(5, 3)
    CHECK_PAIR(5, 6)
    CHECK_PAIR(6, 7)
    CHECK_PAIR(7, 8)
    CHECK_PAIR(4, 8)
    return true;
}


bool test6(int x, int y)
{
    return    BEFORE(0, 1)
           || BEFORE(0, 2)
           || BEFORE(1, 3)
           || BEFORE(1, 4)
           || BEFORE(2, 5)
           || BEFORE(2, 6)
           || BEFORE(3, 7)
           || BEFORE(3, 8);
}

bool check6(int n, int *a, int *a_org)
{
    CHECK_PAIR(0, 1)
    CHECK_PAIR(0, 2)
    CHECK_PAIR(1, 3)
    CHECK_PAIR(1, 4)
    CHECK_PAIR(2, 5)
    CHECK_PAIR(2, 6)
    CHECK_PAIR(3, 7)
    CHECK_PAIR(3, 8)
    return true;
}


int main(int argc, char *argv[])
{
    testSort(9, test1, check1);
    testSort(9, test2, check2);
    testSort(9, test3, check3);
    testSort(9, test4, check4);
    testSort(9, test5, check5);
    testSort(9, test6, check6);
    return 0;
}