#include<iostream.h>

struct node{ int info;

node*next;

node*previous;} *dlistbeg, *dlistend, *p, *q;

node*getnode(int x){

      p=new node;

      p->info=x;

      p->next=NULL;

      p->previous=NULL;

      return p;}//GETNODE

void insertatbeg(node*p){

      p->next=dlistbeg;

      dlistbeg->previous=p;

      dlistbeg=p;}//INSERTATBEG

void insertatend(node*p){

      dlistend->next=p;

      p->previous=dlistend;

      dlistend=p;}//INSERTATEND

void insertinbetween(node*p){

      node*t=dlistbeg;

      while(p->info>t->info)t=t->next;

      p->next=t;

      t->previous->next=p;

      p->previous=t->previous;

      t->previous=p;}//INSERTINBETWEEN

void traverse(node*t){

      while(t!=NULL){

            cout<<t->info<<"";

            t=t->next;}//WHILE

}//TRAVSERSE

void main(){

      int x;

      dlistbeg=dlistend=NULL;

      cout<<"ENTER A NUMBER, -1 TO QUIT: ";

      cin>>x;

      do{

            p=getnode(x);

            if(dlistbeg==NULL) dlistbeg=dlistend=p;

            else if(p->info<dlistbeg->info) insertatbeg(p);

            else if(p->info<dlistend->info) insertatend(p);

            else insertinbetween(p);

            cout<<"ENTER A NUMBER, -1 TO QUIT: ";

            cin>>x;}while(x!=-1);

            traverse(dlistbeg);

}//MAIN