var 9

#include "pch.h"
#include <iostream>
#include  <time.h>
struct tochd
{
    int inf;
    tochd *l;
    tochd *r;
};
using namespace std;
void NewOchd(tochd **sl, tochd **sr) {
    *sl = new tochd;
    *sr = new tochd;
    (*sl)->l = NULL;
    (*sl)->r = *sr;
    (*sr)->l = *sl;
    (*sr)->r = NULL;
}

void AddOchdR(tochd *sp, int inf) {
    tochd *spt = new tochd;
    spt->inf = inf;
    spt->l = sp;
    spt->r = sp->r;
    sp->r->l = spt;
    sp->r = spt;
}
void AddOchdL(tochd *sp, int inf) {
    tochd *spt = new tochd;
    spt->inf = inf;
    spt->l = sp->l;
    spt->r = sp;
    sp->l->r = spt;
    sp->l = spt;
}
int ReadOchdD(tochd *sp) {
    int inf = sp->inf;
    sp->l->r = sp->r;
    sp->r->l = sp->l;
    delete sp;
    return inf;
}
void DelOchdAll(tochd **sl, tochd **sr)
{
    tochd *spt = (*sl)->r;
    while (spt != *sr)
    {
        cout << ReadOchdD(spt) << " ";
        spt = (*sl)->r;
    }
    cout << endl; *sl = NULL;
    delete *sl; *sr = NULL;
    delete *sr;
    return;
}
void div2Ochd(tochd *sl, tochd *sr, tochd **slL,
    tochd **srL, tochd **slR, tochd **srR) {
    NewOchd(slL, srL);
    NewOchd(slR, srR);
    tochd *spt = sl->r;
    while (spt != sr)
    {
        AddOchdL(*srL, ReadOchdD(spt));
        spt = sl->r;
        if (spt != sr)
        {
            AddOchdL(*srR, ReadOchdD(spt));
            spt = sl->r;
        }
    }
}

void slipOchd(tochd **sl, tochd **sr, tochd *slL, tochd *srL, tochd
    *slR, tochd *srR)
{
    NewOchd(sl, sr);
    tochd *sptL = slL->r;
    tochd *sptR = slR->r;
    while ((sptL != srL) && (sptR != srR))
    {
        if (sptL->inf < sptR->inf)
        {
            AddOchdL(*sr, ReadOchdD(sptL));
            sptL = slL->r;
        }
        else
        {
            AddOchdL(*sr, ReadOchdD(sptR));
            sptR = slR->r;
        }
    }
    while (sptL != srL)
    {
        AddOchdL(*sr, ReadOchdD(sptL));
        sptL = slL->r;
    }
    delete slL; delete srL;
    while (sptR != srR)
    {
        AddOchdL(*sr, ReadOchdD(sptR));
        sptR = slR->r;
    }
    delete slR; delete srR;
}

void SotrSlipOchd(tochd **sl, tochd **sr) {
    tochd *slL, *srL, *slR, *srR;
    if ((*sl)->r == *sr || (*sl)->r->r == *sr) return;
    div2Ochd(*sl, *sr, &slL, &srL, &slR, &srR);
    SotrSlipOchd(&slL, &srL);
    SotrSlipOchd(&slR, &srR);
    slipOchd(sl, sr, slL, srL, slR, srR);
}


int main()
{
    setlocale(LC_ALL, "Russian");
    srand(time(NULL));
    int n;
    cout << "Введите количество элементов ";
    cin >> n;
    tochd *sl, *sr;
    NewOchd(&sl, &sr);
    tochd *t = new tochd;// временная , которая указывает на макс элемент
    t->inf = 51;

    for (int i = 0; i < n; i++) {
        int temp = rand() % 101 - 50;
        cout << temp << " ";

        AddOchdL(sr, temp);
        if (temp < t->inf) t = sr->l;// поиск макс элемента, присваиваем предпоследний так как списки имеют вид NULL<->-842...<->(наши список)<->-842...<->NULL
    }
    cout << endl;
    if (t->r == NULL || t->l == NULL) {// проверка если наш элемент стоит у края, то удаляем его, иначе соседей
        t->r->l = t->l;
        t->l->r = t->r;
    }
    else {
        t->r->r->l = t;
        t->r = t->r->r;
        t->l->l->r = t;
        t->l = t->l->l;
    }
    t = sl->r;
    while (t != sr) {

        cout << t->inf << " ";
        t = t->r;
    }
    cout << endl;
    tochd *spt = sl->r;
    int x = 14;
    int pos = 1;
    while (spt != sr && spt->inf != x) {
        pos++;
        spt = spt->r;
    }
    if (spt != sr) {
        cout << "Элемент с моим вариантом находится на "<<pos <<" позиции"<< endl;
    }
    else {
        cout << "Нет моего варианта" << endl;
    }
    SotrSlipOchd(&sl, &sr);
    DelOchdAll(&sl, &sr);
    return 0;
}