#include <cstdio>
#include <Windows.h>

typedef struct
{
    int Info;
    LIST_ENTRY ListEntry;
}NODE, *PNODE;

typedef void(*SWAP_FUNCTION)(
    _In_ PLIST_ENTRY Src,
    _In_ PLIST_ENTRY Dst
 );

void InitializeListHead(_Inout_ PLIST_ENTRY Head)
{
    Head->Flink = Head;
    Head->Blink = Head;
}

void InsertAtBeginningElement(_In_ int ElementValue, _Inout_ PLIST_ENTRY Head)
{
    PNODE newNode = (PNODE)malloc(sizeof(NODE)); // allocate new node
    if (newNode == NULL)
    {
        printf("Malloc failed! %d ", GetLastError());
        return;
    }
    newNode->Info = ElementValue;
    newNode->ListEntry.Blink = Head;

    PLIST_ENTRY lostElement = Head->Flink; // save element
    Head->Flink = &newNode->ListEntry; // points to the new node

    lostElement->Blink = &newNode->ListEntry; // points to the new first element

    newNode->ListEntry.Flink = lostElement;

    if (Head->Blink == Head) // list is empty
    {
        Head->Blink = &newNode->ListEntry;
    }

}

void SwapValues(
    _In_ PLIST_ENTRY Src,
    _In_ PLIST_ENTRY Dst)
{
    PNODE src = CONTAINING_RECORD(Src, NODE, ListEntry);
    PNODE dst = CONTAINING_RECORD(Dst, NODE, ListEntry);

    int aux = src->Info;
    src->Info = dst->Info;
    dst->Info = aux;
}

void SwapLinks(
    _In_ PLIST_ENTRY Src,
    _In_ PLIST_ENTRY Dst)
{
    PLIST_ENTRY bSrc = Src->Blink;
    PLIST_ENTRY fSrc = Src->Flink;

    PLIST_ENTRY bDst = Dst->Blink;
    PLIST_ENTRY fDst = Dst->Flink;

    if (Src->Flink == Dst)
    {
        Src->Flink = fDst;
        Src->Blink = Dst;

        bSrc->Flink = Dst;
        Dst->Blink = bSrc;

        fDst->Blink = Src;
        Dst->Flink = Src;

        return;
    }

    bSrc->Flink = Dst;
    fSrc->Blink = Dst;
    Dst->Flink = fSrc;
    Dst->Blink = bSrc;

    bDst->Flink = Src;
    fDst->Blink = Src;
    Src->Flink = fDst;
    Src->Blink = bDst;
}

PLIST_ENTRY Partition(
    _Inout_ PLIST_ENTRY Start,
    _Inout_ PLIST_ENTRY End,
    _In_ SWAP_FUNCTION SwapFunction)
{
    int pivotElem = CONTAINING_RECORD(End, NODE, ListEntry)->Info;
    PLIST_ENTRY pivot = Start;
    for (PLIST_ENTRY iter = Start; iter != End; iter = iter->Flink)
    {
        PNODE elem = CONTAINING_RECORD(iter, NODE, ListEntry);
        if (pivotElem > elem->Info)
        {
            SwapFunction(pivot, iter);
            pivot = pivot->Flink;
        }
    }

    SwapFunction(pivot, End);
    return pivot;
}

void QSort(
    _In_ PLIST_ENTRY Head,
    _In_ PLIST_ENTRY Start,
    _In_ PLIST_ENTRY End,
    _In_ SWAP_FUNCTION SwapFunction)
{
    if (Start == End || Start == Head || End == Head || Start->Blink == End )
    {
        return;
    }
    PLIST_ENTRY pivot = Partition(Start, End, SwapFunction);
    QSort(Head, Start, pivot->Blink, SwapFunction);
    QSort(Head, pivot->Flink, End, SwapFunction);
}

void SortList(_In_ PLIST_ENTRY Head, _In_ SWAP_FUNCTION SwapFunction)
{
    QSort(Head, Head->Flink, Head->Blink, SwapFunction);
}

void PrintList(_In_ PLIST_ENTRY Head)
{
    PLIST_ENTRY current = Head->Flink;

    while (current != Head)
    {
        PNODE currentElement = (PNODE)CONTAINING_RECORD(current, NODE, ListEntry);
        printf("%d ", currentElement->Info);
        current = current->Flink;
    }
}

void ReadList(_Inout_ PLIST_ENTRY Head)
{
    int n;
    scanf_s("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int x;
        scanf_s("%d", &x);
        InsertAtBeginningElement(x, Head);
    }

}

int main()
{
    LIST_ENTRY head = { 0 };
    InitializeListHead(&head);
    ReadList(&head);



    SortList(&head, &SwapValues);
    PrintList(&head);


    printf("\n");
    SortList(&head, &SwapLinks);
    PrintList(&head);



    return 0;
}