动态第 k 小查询（动态开点值域线段树）

题目描述

你需要维护一个初始为空的多重集合 (S)（允许重复元素）。

接下来有 (Q) 个操作，操作类型如下：

• 添加操作：给定整数 (x)，将 (x) 插入集合 (S)。
• 查询操作：给定整数 (k)，查询集合 (S) 中第 (k) 小的元素（按从小到大排序，重复元素按出现次数计入）。 若当前集合元素个数小于 (k)，则输出 invalid。

你需要按顺序处理所有操作，并输出所有查询操作的结果。

输入格式

• 第一行包含一个整数 (Q)（表示操作次数）。
• 接下来 (Q) 行，每行表示一个操作，格式为以下两种之一：

1. 1 x：表示将整数 (x) 插入集合 (S)
2. 2 k：表示查询集合 (S) 中第 (k) 小的元素

输出格式

对于每个查询操作 2 k：

• 如果集合中元素个数 \((\ge k)\)，输出第 (k) 小的元素值；
• 否则输出 invalid。

数据范围（输入数据制约）

• \((1 \le Q \le 3 \times 10^5)\)
• 对于添加操作：\((1 \le x \le 10^9)\)
• 对于查询操作：\((1 \le k \le 3 \times 10^5)\)
• 集合允许重复插入相同的 (x)

示例

输入示例 1

8
1 5
1 2
1 7
2 1
2 2
1 2
2 2
2 4

输出示例 1

2
5
2
7

说明

以上示例中：

• 插入 (5,2,7) 后集合为 ({2,5,7})
• 第 1 小为 2，第 2 小为 5
• 再插入 2 后集合为 ({2,2,5,7})
• 第 2 小为 2，第 4 小为 7