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

// Doubly linked list node
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) exit(1);
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Insert in descending order
void insertSorted(Node** head, int data) {
    Node* newNode = createNode(data);

    // Insert at head if list empty or new data is >= head
    if (*head == NULL || (*head)->data <= data) {
        newNode->next = *head;
        if (*head) (*head)->prev = newNode;
        *head = newNode;
        return;
    }

    Node* current = *head;
    while (current->next && current->next->data > data) {
        current = current->next;
    }

    newNode->next = current->next;
    if (current->next) current->next->prev = newNode;
    current->next = newNode;
    newNode->prev = current;
}

// Delete middle (first middle if even)
void deleteMiddle(Node** head) {
    if (*head == NULL) return;

    Node* slow = *head;
    Node* fast = *head;

    while (fast->next && fast->next->next) {
        fast = fast