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 <bits/stdc++.h>


template<typename T>
struct AVL{
    struct Node{
        Node* l;
        Node* r;
        Node* p;
        T val;
        int height;
        int size;

        Node(T val, Node* nil) : val(val), height(0), size(1), l(nil), r(nil), p(nil){}

        bool is_nil(){return p == nullptr;}

        void fetch(){
            if(is_nil())
                return;
            size = l->size + r->size + 1;
            height = 1 + std::max(l->height, r->height);
            if(!l->is_nil())
                l->p = this;
            if(!r->is_nil())
                r->p = this;
        }
        int balance_factor(){
            return l->height - r->height;
        }
        Node* rotate_l(){
            Node* new_root = r;
            r = new_root->l;
            new_root->l = this;
            fetch();
            new_root->fetch();
            return new_root;
        }
        Node* rotate_r(){
            Node* new_root = l;
            l = new_root->r;
            new_root->r = this;
            fetch();
            new_root->fetch();
            return new_root;
        }
        Node* balance(){
            int diff = balance_factor();
            if(diff == 2){
                if(l->balance_factor() < 0)
                    l = l->rotate_l();
                return rotate_r();
            }
            else if(diff == -2){
                if(r->balance_factor() > 0)
                    r = r->rotate_r();
                return rotate_l();
            }
            fetch();
            return this;
        }
    };
    Node* nil;
    AVL(T nil_val = T()){
        nil = new Node(nil_val, nullptr);
        nil->size = 0;
        nil->l = nil->r = nil;
    }
    std::pair<Node*,Node*> remove_rightest(Node* node){
        if(node->r != nil){
            Node* removed_node;
            std::tie(node->r, removed_node) = remove_rightest(node->r);
            return {node->balance(), removed_node};
        }
        else{
            return {node->l, node};
        }
    }
    Node* merge_with_node(Node* l, Node* root, Node* r){
        int diff = l->height - r->height;
        if(std::abs(diff) <= 1){
            root->l = l;
            root->r = r;
            root->fetch();
            return root;
        }
        else if(diff > 0){
            l->r = merge_with_node(l->r, root, r);
            return l->balance();
        }
        else{
            r->l = merge_with_node(l, root, r->l);
            return r->balance();
        }
    }
    Node* merge(Node* l, Node* r){
        if(l == nil)
            return r;
        Node* removed_node;
        std::tie(l, removed_node) = remove_rightest(l);
        return merge_with_node(l, removed_node, r);
    }
    std::pair<Node*, Node*> split(Node* node, int idx){
        if(node == nil)
            return {nil, nil};
        Node* l = node->l;
        Node* r = node->r;
        node->l = node->r = nil;
        node->fetch();
        int l_size = l->size;
        if(idx < l_size){
            std::pair<Node*, Node*> res = split(l, idx);
            return {res.first, merge_with_node(res.second, node, r)};
        }
        else if(l_size < idx){
            std::pair<Node*, Node*> res = split(r, idx - l_size - 1);
            return {merge_with_node(l, node, res.first), res.second};
        }
        else{
            return {l, merge_with_node(nil, node, r)};
        }
    }
    Node* make_node(int val){
        return new Node(val, nil);
    }
    int get_idx(Node* node, Node* root){
        if(node == nil)
            return -1;
        if(node == root)
            return root->l->size;
        int idx = node->l->size;
        while(node != root){
            Node* par = node->p;
            if(par->r == node)
                idx += par->l->size + 1;
            node = par;
        }
        return idx;
    }
    Node* insert_idx(Node* root, int idx, int val){
        Node* l;
        Node* r;
        std::tie(l, r) = split(root, idx);
        return merge(l, merge(make_node(val), r));
    }
    Node* insert_next(Node* root, Node* target, int val){
        return insert_idx(root, get_idx(target, root) + 1, val);
    }
    Node* search_max(Node* root, std::function<bool(Node*)> func){
        if(root == nil)
            return nil;
        if(func(root)){
            Node* res = search_max(root->r, func);
            if(res != nil)
                return res;
            else
                return root;
        }
        else{
            return search_max(root->l, func);
        }
    }
    Node* search_min(Node* root, std::function<bool(Node*)> func){
        if(root == nil)
            return nil;
        if(func(root)){
            Node* res = search_min(root->l, func);
            if(res != nil)
                return res;
            else
                return root;
        }
        else{
            return search_min(root->r, func);
        }
    }
};

struct PositionHeap{
    struct Node{
        int label;
        char par_label;
        Node* par;
        std::map<char,Node*> ch, prefix_link;
        Node(int label, Node* par = nullptr, char par_label = 0) : label(label), par(par), par_label(par_label){}
    };
    int n;
    Node* root;
    Node* bef_leaf;
    AVL<AVL<int>::Node*> sa_avl;
    AVL<int> data_avl;
    PositionHeap() : n(0){
        root = bef_leaf = new Node(0);
    }
    PositionHeap(std::string s) : n(0){
        root = bef_leaf = new Node(0);
        for(int i = 1; i <= s.size(); ++i)
            add_front(s.at(s.size() - i));
    }
    std::string get_str(Node* node){
        std::string s;
        while(node != root){
            s.push_back(node->par_label);
            node = node->par;
        }
        std::reverse(s.begin(), s.end());
        return s;
    }
    void add_front(char c){
        n++;
        Node* node = bef_leaf;
        std::stack<std::pair<Node*, char>> path_nodes;
        while(node->prefix_link.find(c) == node->prefix_link.end()){
            if(node == root){
                bef_leaf = new Node(n, node, c);
                node->ch.emplace(c, bef_leaf);
                root->prefix_link.emplace(c, bef_leaf);
                std::cout << n << ": " << get_str(bef_leaf) << std::endl;
                return;
            }
            path_nodes.emplace(node, node->par_label);
            node = node->par;
        }
        // prefix linkの先
        node = node->prefix_link.at(c);

        while(!path_nodes.empty()){
            Node* link_node;
            char ch_label;
            std::tie(link_node, ch_label) = path_nodes.top();
            path_nodes.pop();
            auto iter = node->ch.find(ch_label);
            if(iter == node->ch.end()){
                bef_leaf = new Node(n, node, ch_label);
                node->ch.emplace(ch_label, bef_leaf);

                /*
                if(!path_nodes.empty()){
                    std::cout << get_str(link_node) << " => ";
                    link_node = path_nodes.top().first;
                    path_nodes.pop();
                    */
                bef_leaf->prefix_link.emplace(c, link_node);
                std::cout << n << ": " << get_str(bef_leaf) << std::endl;
                return;
            }
            node = iter->second;
            node->prefix_link.emplace(c, link_node);
        }
        exit(1);
    }
};


signed main(){
    int q;
    std::cin >> q;
    AVL<int> avl(-1);
    AVL<int>::Node* root = avl.nil;
    for(int i = 0; i < q; ++i){
        int ty, x;
        std::cin >> ty >> x;
        if(ty == 0){
            AVL<int>::Node* target = avl.search_max(root, [x](AVL<int>::Node* node){return node->val <= x;});
            if(target->val != x){
                root = avl.insert_next(root, target, x);
            }
            /*
            std::cout << "=--------=" << std::endl;
            AVL::print(root);
            AVL::print_all(root);
            std::cout << "\n=--------=\n" << std::endl;
            */
            std::cout << root->size << std::endl;
        }
        else{
            AVL<int>::Node* target = avl.search_max(root, [x](AVL<int>::Node* node){return node->val <= x;});
            std::cout << (target->val == x) << std::endl;
        }

    }
}

