Sequence Query

AtCoder

IDabc241_d

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

API Response (JSON)

{
  "problem": {
    "name": "Sequence Query",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc241_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have an empty sequence $A$.  \nGiven $Q$ queries, process them in order.  \nEach query is of one of the following three types.\n\n*   `1 x` : Insert $x$ to $A$.\n    \n*   `2 x k` : Among the elements of...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments