#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Elem
{
    struct Elem *next;
    char *str;
};


struct Elem *newElem(char *str) {
    struct Elem *newN = (struct Elem*) malloc(sizeof(struct Elem));
    if (newN == NULL)
        return NULL;
    if (str == NULL)
        newN->str = NULL;
    else {
        newN->str = (char*)malloc(strlen(str) + 1);
        strcpy(newN->str, str);
    }
    newN->next = NULL;
    return newN;
}

struct Elem *process_3(struct Elem *head, char *str, int precount) {
    //первый элемент
    if (head == NULL) {
        head = newElem(str);
        return head;
    }
    struct Elem *tmp = head;
    int number = 1;
    //вставка в начало
    if (strcmp(head->str, str) > 0) {
        tmp = newElem(str);
        tmp->next = head;
        head = tmp;
        return head;
    }
    //поиск после какого элемента надо вставить
    while(tmp->next != NULL && strcmp((tmp->next)->str, str) < 0) {
        number++;
        tmp = tmp->next;
    }
    if (tmp->next == NULL || (tmp->next != NULL && strcmp((tmp->next)->str, str) > 0)) {
        //вставка в конец
        if (tmp->next == NULL) {
            tmp->next = newElem(str);
        } else {
            struct Elem *elem = newElem(str);
            elem->next = tmp->next;
            tmp->next = elem;
        }
        if (precount < 0)
            precount = 0;
        int first_delete = number - precount;
        if (precount > number)
            first_delete = 0;
        tmp = head;
        int i = 0;
        if (first_delete == 0 && precount != 0) {
            while (i != number) {
                i++;
                head = head->next;
                free(tmp->str);
                free(tmp);
                tmp = head;
            }
        } else {
            while (i != first_delete - 1) {
                i++;
                tmp = tmp->next;
            }
            i = 0;
            while (i != number - first_delete) {
                struct Elem *tmp2 = tmp->next;
                tmp->next = (tmp2->next);
                free(tmp2->str);
                free(tmp2);
                i++;
            }
        }

    }
    return head;
}