U241769 平衡树性能测试（随机数据）

对于完全**随机**的数据，目前排名： 01. 离线+离散化+树状数组，时间 ``1.40s`` （时间 $O(m\log m)$ ，空间 $O(m)$ ）。 02. 普通二叉查找树，时间 ``2.50s`` （时间 $O(m^2)$ ？？？，空间 $O(m)$ ）。 03. 旋转Treap ，五次平均时间 ``2.68s`` ，（时间 $O(m\log m)$ ，空间 $O(m)$ ）。 04. STL::set，时间 ``2.71s`` （时间 $O(m\log m)$ ，空间 $O(m)$ ）。 05. 块状链表，时间 ``2.80s`` （时间 $O(m\sqrt m)$ ？？？，空间 $O(m)$ ）。 06. 01Trie，时间 ``3.12s`` （时空均 $O(m\log w)$ ）。 08. 非旋Treap，五次平均时间 ``3.37s`` （时间 $O(m\log m)$ ，空间 $O(m)$ ）。 07. Splay，时间 ``3.43s`` （时间 $O(m\log m)$ ，空间 $O(m)$ ）。 09. 动态加点权值线段树，时间 ``3.52`` （时空均 $O(m\log w)$ ）。 10. 暴力，挂了捏（时间 $O(m^2)$ ，空间 $O(m)$ ）。 均开了 O2 。 随机数据下最快的在线算法竟然是——朴素的BST！！

维护一个可重集合，初始为空，有两种操作： ``0 x`` 插入 $x$ 。 ``1 x`` 查询 $x$ 的前驱（比 $x$ 小且最大的数），若没有输出 $-1$ 。 现在给定操作数 $m$ 和 $m$ 个操作，回答所有询问。

第一行一个正整数 $m$ ，表示操作数量。 接下来 $m$ 行，每行两个整数，表示操作。

对于所有操作 $1$ ，输出答案（一行一个）。

$1\leq m\leq 1\times 10^6,\ 0\leq x < 2^{29}$