#include <iostream>
#include <clocale>
#include <cstdlib>
#define LIST
#ifdef LIST
#include "deque_list.cpp"
#else
#include "deque_vectr.cpp"
#endif



using namespace std;

int prime(DataType);

int main()
{
    Dek first, second;
    DataType element;
    int n, k, i;

    cout << "Please, enter number of the elements: " << endl;
    cin >> n;

    cout << "Please, enter elements: " << endl;
    for( i = 0;i < n;i++)
    {
        cin >> element;
        first.AddLast(element);
    }

    k = n;
    for(i=0; i<n; i++)
    {
        if (prime(first.ShowFirst())==0)
            first.AddLast(first.ShowFirst());
        else
            k--;
        first.DeleteFirst();
    }


    if(!first.Empty())
    {
        cout<<"Dek is empty"<<endl;
        return 0;
    }

   //сортировка дека
   second.AddLast(first.ShowFirst());
   first.DeleteFirst();

for(i=0;i<k-1;i++)
    {

       if(first.ShowFirst()<=second.ShowBack()&& first.Empty())
        {
             second.AddLast(first.ShowFirst());

        }//ставит назад
        if(first.ShowFirst()>=second.ShowBack()&& first.Empty())
        {
            second.AddFirst(first.ShowFirst());
        }//ставить вперед
        if(first.ShowFirst()<=second.ShowFirst() && first.ShowFirst()>=second.ShowBack() && first.Empty())
        {
            n=0;
            while(first.ShowFirst()<=second.ShowFirst() && first.ShowFirst()>=second.ShowBack() && first.Empty())
               {
                  second.AddLast(second.ShowFirst());
                 second.DeleteFirst();
                  n++;
               }
           second.AddFirst(first.ShowFirst());

            for(;n>0;n--)
            {
                second.AddFirst(second.ShowBack());
                second.DeleteLast();
            }

        }first.DeleteFirst();
    }
    for(i=0;i<k;i++)
{
    cout<< second.ShowFirst()<<"    ";

}
    system("pause");
    return 0;
}

int prime(DataType element)
{
    int i;
    if(element==1) return 0;
    for(i=2; i<element; i++)
        if(element%i==0)
            return 0;
    return 1;
}

#include <iostream>
#include <cstdlib>

using namespace std;

typedef int DataType;
struct Element
        {
            DataType data;
            struct Element * next, *prev;
        };
typedef struct Element Element;
class Dek
{

       Element *Begin, *End;


public:
    Dek();
    ~Dek();
    void AddFirst(DataType);
    void AddLast(DataType);
    DataType DeleteFirst(void);
    DataType DeleteLast(void);
    DataType ShowFirst(void);
    DataType ShowBack(void);
    int Empty (void);
};
Dek :: Dek()
{
    Begin = End = NULL;;
}
Dek:: ~Dek()
{
     Element * temp;
     while (Begin) //пока в списке есть элементы
     {
           temp=Begin;
           Begin = Begin->next; //переставляем указатель на следующий элемент
           delete temp; //первый удаляем
     }
}
void Dek:: AddFirst(DataType element)
{
       Element * temp;
       temp = new Element;
       temp->data = element;
       temp->next = Begin;
       temp->prev = NULL;
       if (Begin) //если добавляем в непустой список
          Begin->prev = temp;
       else //если добавляемый элемент единственный в списке
          End = temp;
       Begin = temp;
}

void Dek:: AddLast (DataType element)
{
       Element * temp;
       temp = new Element;
       temp->data = element;
       temp->next = NULL;
       temp->prev = End;
       if (End) //если добавляем в непустой список
          End->next = temp;
       else //если добавляемый элемент единственный в списке
          Begin = temp;
       End = temp;
}
DataType Dek:: DeleteFirst(void)
{
     Element * temp;
     DataType element;


     if (Begin == NULL)
     {
        End = NULL;
        return -3;
     }
     element=Begin->data;
    if (Begin!=End) //если в списке есть элементы
     {
           temp = Begin;
           Begin = Begin->next; //переставляем указатель на следующий элемент
           Begin->prev = NULL; //обнуляем указатель на удаляемый элемент
           delete temp; //первый удаляем

     }

    return element;

}
DataType Dek:: DeleteLast(void)
{
    Element * temp;
     DataType element;

     if (Begin == NULL)
     {
        End = NULL;
        return -3;
     }
     element=End->data;
     if (End!=Begin) //если в списке есть элементы
     {
           temp = End;
           End = End->prev; //переставляем указатель на следующий элемент
           End->next = NULL; //обнуляем указатель на удаляемый элемент
           delete temp; //первый удаляем

     }

    return element;
}
int Dek:: Empty (void)
{
    if(Begin==NULL)
        return 0;
    else
        return 1;
}


 DataType Dek:: ShowFirst(void)
 {
     return Begin->data;
 }
  DataType Dek:: ShowBack(void)
 {
     return End->data;
 }