题号：NC17318
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
维护一棵初始为空的红黑树，进行n次操作。
对于重复的整数，我们认为插入时间晚的一个更小。
操作有两类：
op=1：在红黑树上插入一个整数x；
op=2：给出x，询问从1到x的整数中等概率选取一个插入到红黑树上，造成的旋转次数的期望值，方便起见，你只要输出 期望值*x，（可以证明这是一个整数）。
输入描述:
第一行一个整数n；
接下来n行，每行两个由空格分隔的整数op,x，表示一次操作。
1≤n≤200000
1≤op≤2
1≤x≤100000000
输出描述:
对每个op=2的操作，输出一行，包含一个整数，表示答案
示例1
输入
复制
10
2 5
1 3
1 4
2 3
2 4
2 5
1 4
2 3
2 4
2 5