For a set $S$ of integers, perform a sequence of the following operations. Note that each value in $S$ must be unique.

* insert($x$): Insert $x$ to $S$ and report the number of elements in $S$ after the operation.
* find($x$): Report the number of $x$ in $S$ (0 or 1).

Constraints

* $1 \leq q \leq 200,000$
* $0 \leq x \leq 1,000,000,000$

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $x$


or


1 $x$


where the first digits 0 and 1 represent insert and find operations respectively.

Output

For each insert operation, print the number of elements in $S$.
For each find operation, print the number of specified elements in $S$.

Example

Input

7
0 1
0 2
0 3
0 2
0 4
1 3
1 10


Output

1
2
3
3
4
1
0
#include <iostream>
#include <queue>

int flag;

class RedBlackTree{
public:
	class Node{
	public:
		bool Red;
		int Key;
		Node *Left, *Right, *Parent;
		Node(int k){
			Red = false; // true <-> red, false <-> black
			Key = k;
			Left = Right = Parent = nullptr;
		}
	};

	Node *Root, *NIL;
	int Size;

	RedBlackTree(){
		NIL = new Node(0);
		Root = NIL->Parent = NIL->Right = NIL->Left = NIL;
		Size = 0;
	}

	void LeftRotate(Node *x){
		Node *y = x->Right;
		x->Right = y->Left;
		if(y->Left != NIL) y->Left->Parent = x;
		y->Parent = x->Parent;
		if(x->Parent == NIL) Root = y;
		else if(x == x->Parent->Left) x->Parent->Left = y;
		else x->Parent->Right = y;
		y->Left = x;
		x->Parent = y;
	}

	void RightRotate(Node *x){
		Node *y = x->Left;
		x->Left = y->Right;
		if(y->Right != NIL) y->Right->Parent = x;
		y->Parent = x->Parent;
		if(x->Parent == NIL) Root = y;
		else if(x == x->Parent->Left) x->Parent->Left = y;
		else x->Parent->Right = y;
		y->Right = x;
		x->Parent = y;
	}

	Node *Insert(int v){
		Node *y = NIL;
		Node *x = Root;
		while(x != NIL){
			y = x;
			if(x->Key == v) return x;
			if(v < x->Key) x = x->Left;
			else x = x->Right;
		}
		++Size;
		Node *z = new Node(v);
		z->Red = true;
		z->Left = z->Right = z->Parent = NIL;
		z->Parent = y;
		if(y == NIL) Root = z;
		else if(z->Key < y->Key) y->Left = z;
		else y->Right = z;
		if(flag){
			std::cerr << "Before Fixup\n";
			Print();
		}
		InsertFixup(z);
		return z;
	}

	void InsertFixup(Node *z){
		while(z->Parent->Red){
			if(flag){
				std::cerr << "Key = " << z->Key << "\n";
				Print();
			}
			if(z->Parent == z->Parent->Parent->Left){
				if(flag){
					std::cerr << "Left\n";
				}
				Node *y = z->Parent->Parent->Right;
				if(y->Red){
					z->Parent->Red = false;
					y->Red = false;
					z->Parent->Parent->Red = true;
					z = z->Parent->Parent;
				}else if(z == z->Parent->Right){
					z = z->Parent;
					if(flag) std::cerr << "LR\n";
					LeftRotate(z);
				}else{
					z->Parent->Red = false;
					z->Parent->Parent->Red = true;
					if(flag) std::cerr << z->Parent->Parent->Key << " RR\n";
					RightRotate(z->Parent->Parent);
				}
			}else{
				if(flag){
					std::cerr << "Right\n";
				}
				Node *y = z->Parent->Parent->Left;
				if(y->Red){
					z->Parent->Red = false;
					y->Red = false;
					z->Parent->Parent->Red = true;
					z = z->Parent->Parent;
				}else if(z == z->Parent->Left){
					z = z->Parent;
					RightRotate(z);
				}else{
					z->Parent->Red = false;
					z->Parent->Parent->Red = true;
					LeftRotate(z->Parent->Parent);
				}
			}
		}
		Root->Red = false;
	}

	Node *Search(int k){
		Node *x = Root;
		while(x != NIL){
			if(x->Key == k) break;
			else if(x->Key < k) x = x->Right;
			else x = x->Left;
		}
		return x;
	}

	void InorderTreeWalk(Node *x, std::queue<int> &q){
		if(x == NIL) return;
		InorderTreeWalk(x->Left, q);
		q.push(x->Key);
		InorderTreeWalk(x->Right, q);
	}

	void PreorderTreeWalk(Node *x, std::queue<int> &q){
		if(x == NIL) return;
		q.push(x->Key);
		PreorderTreeWalk(x->Left, q);
		PreorderTreeWalk(x->Right, q);
	}
	
	void Print(){
		std::cerr << "Size = " << Size << "\n";
		Print(Root, 0, 0);
	}

	void Print(Node *x, int dep, int lr){
		if(x == NIL) return;
		Print(x->Right, dep+1, 1);
		for(int i=0; i<dep; i++) std::cerr << "  ";
		if(!lr) std::cerr << "--";
		else if(lr == 1) std::cerr << "|‾";
		else std::cerr << "|_";
		if(x->Red) std::cerr << "\x1b[31m";
		std::cerr << x->Key << std::endl;
		std::cerr << "\x1b[0m";
		Print(x->Left, dep+1, 2);
	}
};

int main(){
//	std::cin.tie(0);
//	std::ios::sync_with_stdio(false);
	int q;
	std::cin >> q;
	RedBlackTree rbt;
	while(q--){
		int x, y;
		std::cin >> x >> y;
		if(x == 0){
			rbt.Insert(y);
			std::cout << rbt.Size << "\n";
		}else if(x == 1){
			std::cout << (rbt.Search(y) == rbt.NIL ? 0 : 1) << "\n";
		}else{
			rbt.Print();
			flag = 1 - flag;
			std::cerr << "\n";
			++q;
		}
	}
}
