---

#include <iostream>
#include <cstdlib>   // для rand() и srand()
#include <ctime>     // для time()
using namespace std;

struct tochd {
    int inf;
    tochd *left;
    tochd *right;
};

// ---- Базовая функция вывода списка на экран ----
void PrintOchd(tochd *sl, tochd *sr) {
    tochd *spt = sl->right;
    while (spt != sr) {
        cout << spt->inf << " ";
        spt = spt->right;
    }
    cout << endl;
}

// ---- Функции из лабораторной ----
void NewOchd(tochd **sl, tochd **sr) {
    *sl = new tochd;
    *sr = new tochd;
    (*sl)->left = NULL;
    (*sl)->right = *sr;
    (*sr)->left = *sl;
    (*sr)->right = NULL;
}

void AddOchdRight(tochd *sp, int inf) {
    tochd *spt = new tochd;
    spt->inf = inf;
    spt->left = sp;
    spt->right = sp->right;
    sp->right = spt;
    spt->right->left = spt;
}

void AddOchdLeft(tochd *sp, int inf) {
    tochd *spt = new tochd;
    spt->inf = inf;
    spt->left = sp->left;
    spt->right = sp;
    spt->left->right = spt;
    sp->left = spt;
}

int ReadOchdD(tochd *sp) {
    int inf = sp->inf;
    sp->left->right = sp->right;
    sp->right->left = sp->left;
    delete sp;
    return inf;
}

void DelOchdAll(tochd **sl, tochd **sr) {
    tochd *spt = (*sl)->right;
    while (spt != *sr) {
        ReadOchdD(spt);
        spt = (*sl)->right;
    }
    delete *sl;
    *sl = NULL;
    delete *sr;
    *sr = NULL;
}

// ---- Генерация списка со случайными числами ----
void FillRandomOchd(tochd *sr, int n, int min_val = -50, int max_val = 50) {
    for (int i = 0; i < n; i++) {
        int random_num = min_val + rand() % (max_val - min_val + 1);
        AddOchdLeft(sr, random_num);
    }
}

// ---- Вспомогательная функция: найти указатель на минимальный и максимальный элементы ----
void FindMinMax(tochd *sl, tochd *sr, tochd **min_ptr, tochd **max_ptr) {
    *min_ptr = sl->right;
    *max_ptr = sl->right;
    tochd *spt = sl->right;
    
    while (spt != sr) {
        if (spt->inf < (*min_ptr)->inf)
            *min_ptr = spt;
        if (spt->inf > (*max_ptr)->inf)
            *max_ptr = spt;
        spt = spt->right;
    }
}

// ---- ЗАДАЧА 10 ----
// Удалить элементы, заключенные между максимальным и минимальным значениями
void DeleteBetweenMinMax(tochd *sl, tochd *sr) {
    tochd *min_ptr, *max_ptr;
    FindMinMax(sl, sr, &min_ptr, &max_ptr);
    
    // Если они соседи — удалять нечего
    if (min_ptr->right == max_ptr || max_ptr->right == min_ptr) {
        return;
    }
    
    // Определяем, кто левее
    tochd *left_bound = NULL, *right_bound = NULL;
    tochd *spt = sl->right;
    while (spt != sr) {
        if (spt == min_ptr) {
            left_bound = min_ptr;
            right_bound = max_ptr;
            break;
        }
        if (spt == max_ptr) {
            left_bound = max_ptr;
            right_bound = min_ptr;
            break;
        }
        spt = spt->right;
    }
    
    // Удаляем элементы между left_bound и right_bound (не включая их)
    spt = left_bound->right;
    while (spt != right_bound) {
        tochd *next = spt->right;
        cout << "Удалён элемент: " << ReadOchdD(spt) << endl;
        spt = next;
    }
}

// ---- Пример использования ----
int main() {
    setlocale(LC_ALL, "Russian");
    srand(time(0));  // инициализация генератора случайных чисел
    
    tochd *sl, *sr;
    NewOchd(&sl, &sr);
    
    int n;
    cout << "Введите количество элементов списка: ";
    cin >> n;
    
    // Заполняем список случайными числами в диапазоне [-100, 100]
    FillRandomOchd(sr, n, -100, 100);
    
    cout << "\nИсходный список:" << endl;
    PrintOchd(sl, sr);
    
    tochd *min_ptr, *max_ptr;
    FindMinMax(sl, sr, &min_ptr, &max_ptr);
    cout << "Минимальный элемент: " << min_ptr->inf << endl;
    cout << "Максимальный элемент: " << max_ptr->inf << endl;
    
    DeleteBetweenMinMax(sl, sr);
    
    cout << "\nСписок после удаления элементов между min и max:" << endl;
    PrintOchd(sl, sr);
    
    DelOchdAll(&sl, &sr);
    return 0;
}