---

#include <iostream>
using namespace std;

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

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 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 printOchd(tochd *sl, tochd *sr) {
    tochd *p = sl->right;
    while (p != sr) {
        cout << p->inf << " ";
        p = p->right;
    }
    cout << endl;
}

// Вставка в конец (перед sr)
void addToEnd(tochd *sr, int val) {
    AddOchdLeft(sr, val);
}

// Поиск указателя на максимальный элемент
tochd* findMax(tochd *sl, tochd *sr) {
    tochd *p = sl->right;
    if (p == sr) return nullptr;
    tochd *maxPtr = p;
    int maxVal = p->inf;
    p = p->right;
    while (p != sr) {
        if (p->inf > maxVal) {
            maxVal = p->inf;
            maxPtr = p;
        }
        p = p->right;
    }
    return maxPtr;
}

int main() {
    setlocale(LC_ALL, "Russian");
    tochd *sl, *sr;
    NewOchd(&sl, &sr);

    int n;
    cout << "Введите количество элементов: ";
    cin >> n;
    if (n <= 0) {
        cout << "Список пуст." << endl;
        DelOchdAll(&sl, &sr);
        return 0;
    }
    cout << "Введите элементы: ";
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        addToEnd(sr, val);
    }

    cout << "Исходный список: ";
    printOchd(sl, sr);

    tochd *first = sl->right;          // первый элемент
    tochd *maxPtr = findMax(sl, sr);   // максимальный элемент

    if (!maxPtr) {
        cout << "Список пуст (максимальный не найден)." << endl;
        DelOchdAll(&sl, &sr);
        return 0;
    }

    cout << "Первый элемент: " << first->inf << endl;
    cout << "Максимальный элемент: " << maxPtr->inf << endl;

    if (first == maxPtr) {
        cout << "Первый элемент уже является максимальным, обмен не требуется." << endl;
    } else {
        // Меняем значения, не перемещая узлы в памяти
        int tmp = first->inf;
        first->inf = maxPtr->inf;
        maxPtr->inf = tmp;
        cout << "После обмена первого и максимального: ";
        printOchd(sl, sr);
    }

    DelOchdAll(&sl, &sr);
    return 0;
}