102413: [AtCoder]ABC241 D - Sequence Query

Problem Statement

We have an empty sequence $A$.
Given $Q$ queries, process them in order.
Each query is of one of the following three types.

• 1 x : Insert $x$ to $A$.

• 2 x k : Among the elements of $A$ that are less than or equal to $x$, print the $k$-th largest value. ($k$ is no more than $\bf{5}$)
  If there are less than $k$ elements of $A$ that are less than or equal to $x$, then print -1.

• 3 x k : Among the elements of $A$ that are greater than or equal to $x$, print the $k$-th smallest value. ($k$ is no more than $\bf{5}$)
  If there are less than $k$ elements of $A$ that are greater than or equal to $x$, then print -1.

Constraints

• $1\leq Q \leq 2\times 10^5$
• $1\leq x\leq 10^{18}$
• $1\leq k\leq 5$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

In the $i$-th query $\text{query}_i$, the type of query $c_i$ (which is either $1, 2$, or $3$) is given first.
If $c_i=1$, then $x$ is additionally given; if $c_i=2, 3$, then $x$ and $k$ are additionally given.

In other words, each query is given in one of the following three formats:

$1$ $x$

$2$ $x$ $k$

$3$ $x$ $k$

Output

Print $q$ lines, where $q$ is the number of queries such that $c_i=2,3$.
The $j$-th line $(1\leq j\leq q)$ should contain the answer for the $j$-th such query.

Sample Input 1

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

Sample Output 1

20
20
30
-1
-1
1

After $\text{query}_{1,2,3,4}$ have been processed, we have $A=(20,10,30,20)$.

For $\text{query}_{5,6,7}$, the elements of $A$ greater than or equal to $15$ are $(20,30,20)$.
The $1$-st smallest value of them is $20$; the $2$-nd is $20$; the $3$-rd is $30$.

问题描述

我们有一个空序列$A$。

给定$Q$个查询，按顺序处理它们。

每个查询是以下三种类型之一：

• 1 x：将$x$插入到$A$中。

• 2 x k：在$A$中小于或等于$x$的元素中，打印第$k$个最大的值。（$k$不超过$\bf{5}$）
  如果小于或等于$x$的$A$元素少于$k$个，则打印-1。

• 3 x k：在$A$中大于或等于$x$的元素中，打印第$k$个最小的值。（$k$不超过$\bf{5}$）
  如果大于或等于$x$的$A$元素少于$k$个，则打印-1。

约束

• $1\leq Q \leq 2\times 10^5$
• $1\leq x\leq 10^{18}$
• $1\leq k\leq 5$
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

在第$i$个查询$\text{query}_i$中，首先给出查询类型$c_i$（即1、2或3）。

如果$c_i=1$，则还会给出$x$；如果$c_i=2, 3$，则还会给出$x$和$k$。

换句话说，每个查询采用以下三种格式之一：

$1$ $x$

$2$ $x$ $k$

$3$ $x$ $k$

输出

打印$q$行，其中$q$是查询数，使得$c_i=2,3$。

第$j$行（$1\leq j\leq q$）应包含第$j$个此类查询的答案。

样例输入1

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

样例输出1

20
20
30
-1
-1
1

在$\text{query}_{1,2,3,4}$处理后，我们有$A=(20,10,30,20)$。

对于$\text{query}_{5,6,7}$，$A$中大于或等于$15$的元素为$(20,30,20)$。

它们的第1个最小值是$20$；第2个是$20$；第3个是$30$。