typedef int Key;

typedef struct item{
  Key key;
}Item;

typedef struct table{
  int n;
  Item *item;
}*Table;

int hoge;

Item *lookup_item(Table table,Key key){
  int mid,left,right;
  left=0;
  right=table->n-1;
  while(1) {
		mid = (left + right) / 2;
		if(table->item[mid].key == key){hoge = mid; return &table->item[mid];}
		if(left>=right){hoge = mid; return 0;}
		if (table->item[mid].key < key) left = mid + 1;
		else right = mid-1;
	}
	return 0;
}

int add_item(Table table,Item item){
  int i;

  if(lookup_item(table,item.key) == 0){

	  if(table->n == 0){
		  table->item[0].key = item.key;
		  table->n++;
		  return 1;
	  }

	  if(table->item[table->n-1].key < item.key){
		  table->item[table->n].key = item.key;
		  table->n++;
		  return 1;
	  }

	  if(table->item[0].key > item.key){
		  for(i=table->n;i>0;i--){
			  table->item[i].key = table->item[i-1].key;
		  }
		  table->item[0].key = item.key;
		  table->n++;
		  return 1;
	  }

	  for(i=hoge-1;i<=hoge+1;i++){
		  if(table->item[i-1].key<item.key && item.key<table->item[i].key){
			  hoge = i;
			  break;
		  }
	  }
	  for(i=table->n;i>hoge;i--){
		  table->item[i].key = table->item[i-1].key;
	  }
	  table->item[hoge].key = item.key;
	  table->n++;
	  return 1;
  }
  return 0;
}