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

struct Node {
    char chapter[101];
    struct Node *prev, *next;
};

// Function to create a new node
struct Node* createNode(char *chapter) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    strcpy(newNode->chapter, chapter);
    newNode->prev = newNode->next = NULL;
    return newNode;
}

// Insert node at end
void insertEnd(struct Node **head, struct Node **tail, char *chapter) {
    struct Node* newNode = createNode(chapter);
    if (*head == NULL) {
        *head = *tail = newNode;
    } else {
        (*tail)->next = newNode;
        newNode->prev = *tail;
        *tail = newNode;
    }
}

// Delete node at given position (0-based)
void deleteAtPos(struct Node **head, struct Node **tail, int pos, int n) {
    if (pos >= n) {
        printf("Invalid input\n");
        exit(0);
    }

    struct Node *temp = *head;
    for (int i = 0; i < pos; i++) {
        temp = temp->next;
    }

    if (temp->prev != NULL)
        temp->prev->next = temp->next;
    else
        *head = temp->next;

    if (temp->next != NULL)
        temp->next->prev = temp->prev;
    else
        *tail = temp->prev;

    free(temp);
}

int main() {
    int n, pos;
    scanf("%d", &n);

    struct Node *head = NULL, *tail = NULL;

    for (int i = 0; i < n; i++) {
        char chapter[101];
        scanf("%s", chapter);

        // Validation: must start with alphabet
        if (!isalpha(chapter[0])) {
            printf("Invalid input\n");
            return 0;
        }
        insertEnd(&head, &tail,