#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int val;
	struct node* lnext;
	struct node* rnext;
}node;

void push(node *, int);
int find(node *);
int pop(node *);
void swap(int *,int *);
long cnt=1;

int main()
{
	int a;
	char ch[5];
	node head;
	printf("초기값 설정 ㄱㄱ\n");
	scanf("%d",&head.val);
	head.lnext=NULL;
	head.rnext=NULL;
	for(;;)
	{
		printf("push나 pop이나 exit 입력(push/pop/exit)\n");
		scanf("%s",ch);
		if(ch[0]=='e' && ch[1]=='x' && ch[2]=='i' && ch[3]=='t') break;
		else if(ch[0]=='p' && ch[1]=='u' && ch[2]=='s' && ch[3]=='h')
		{
			printf("넣을 숫자 입력 ㄱㄱ(자연수만) : ");
			scanf("%d",&a);
			push(&head,a);
		}
		else if(ch[0]=='p' && ch[1]=='o' && ch[2]=='p')
		{
			a=find(&head);
			if(a==-1) printf("숫자 없음\n");
			else printf("%d가 있었다\n",a);
		}
		else printf("push나 pop이나 exit만 입력하라고...\n");
	}
	return 0;
}
void swap(int * a, int * b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

void push(node * target, int newval)
{
	node * newnode;
	int a=1,c,i,temp,flag=0;
	int * b;
	cnt++;
	if(cnt==1)
	{
		target->val=newval;
		target->lnext=NULL;
		target->rnext=NULL;
		return;
	}
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	newnode=(node *)malloc(sizeof(node));
	temp=newval;
	for(i=c-2;i>=1;i--)
	{
		if(target->val>newval) swap(&target->val,&newval);
		if(b[i]==0) target=target->lnext;
		else target=target->rnext;
	}
	if(target->val>newval) swap(&target->val,&newval);
	newnode->val=newval,newnode->lnext=NULL,newnode->rnext=NULL;
	if(b[0]==0) target->lnext=newnode;
	else target->rnext=newnode;
	free(b);
}

int find(node * target)
{
	int res,regap;
	node * imsi=(node *)malloc(sizeof(node));
	imsi=target;
	res=pop(target);
	if(res==-1) return -1;
	target=imsi;
	regap=target->val;
	target->val=res;
	while(target->lnext!=NULL || target->rnext!=NULL)
	{
		if(target->lnext!=NULL && target->rnext!=NULL)
		{
			if(target->val>target->lnext->val && target->val>target->rnext->val)
			{
				if(target->lnext->val<=target->rnext->val)
				{
					swap(&target->val,&target->lnext->val);
					target=target->lnext;
				}
				else
				{
					swap(&target->val,&target->rnext->val);
					target=target->rnext;
				}
			}
			else if(target->val>target->lnext->val)
			{
				swap(&target->val,&target->lnext->val);
				target=target->lnext;
			}
			else if(target->val>target->rnext->val)
			{
				swap(&target->val,&target->rnext->val);
				target=target->rnext;
			}
			else break;
		}
		else if(target->lnext!=NULL)
		{
			if(target->val>target->lnext->val)
			{
				swap(&target->val,&target->lnext->val);
				target=target->lnext;
			}
			else break;
		}
		else if(target->rnext!=NULL)
		{
			if(target->val>target->rnext->val)
			{
				swap(&target->val,&target->rnext->val);
				target=target->rnext;
			}
			else break;
		}
		else break;
	}
	return regap;
}

int pop(node * target)
{
	int a=1,c,i;
	int * b;
	if(cnt==0) return -1;
	if(cnt==1)
	{
		cnt--;
		return target->val;
	}
	for(c=1;;c++)
	{
		if(a<=cnt && cnt<2*a) break;
		a*=2;
	}
	a=cnt;
	b=(int *)malloc((sizeof(int))*c);
	for(i=0;i<c;i++)
	{
		if(a%2==0) b[i]=0;
		else b[i]=1;
		a/=2;
	}
	for(i=c-2;i>=1;i--)
	{
		if(b[i]==0)
			target=target->lnext;
		else
			target=target->rnext;
	}
	if(b[0]==0)
	{
		a=target->lnext->val;
		free(target->lnext);
		target->lnext=NULL;
	}
	else
	{
		a=target->rnext->val;
		free(target->rnext);
		target->rnext=NULL;
	}
	free(b);
	cnt--;
	return a;
}