23486번 - Game and Queries 다국어

문제

Alice and Bob are going to play a game. The rule of the game is as follows:

• There are some monsters, each of which has a specified HP.
• Alice and Bob take turns alternately, with Alice going first.
• In Alice's turn, she chooses one of the monsters and increases its HP by 1ドル$.
• In Bob's turn, he chooses one of the monsters and decreases its HP by 2ドル$. If the monster's HP becomes 0ドル$ or less, the monster disappears.
• The game ends when $k$ monsters disappear.

Alice's objective is to finish the game as late as possible, while Bob's is as soon as possible.

Initially, there are no monsters. You have to process $Q$ queries of the following types:

• Type 1ドル$: You are given two integers $X_i$ and $Y_i$. After this query, the number of monsters whose HPs are $X_i$ becomes $Y_i$.
• Type 2ドル$: Given an integer $K_i,ドル calculate how many turns would Bob take if the game started with current monsters and $k=K_i,ドル assuming both players play optimally.

Note that the game doesn't happen in reality, and the monsters don't disappear.

입력

Input is given from Standard Input in the following format:

$Q$

Description of the 1-st query

Description of the 2-nd query

$\vdots$

Description of the Q-th query

The description of each query is in one of the following formats:

Type 1ドル$: 1ドル$ $X_i$ $Y_i$

Type 2ドル$: 2ドル$ $K_i$

출력

For each query of the type 2ドル,ドル print the answer in a line.

제한

• 1ドル \leq Q \leq 3 \times 10^5$
• 1ドル \leq T_i \leq 2$
• 1ドル \leq X_i \leq 10^6$
• 0ドル \leq Y_i \leq 10^6$
• 1ドル \leq K_i \leq ($ the number of current monsters $)$
• There is at least one query of the type 2ドル$
• All values in input are integers.

노트

After the 5ドル$-th query, there are 4ドル$ monsters whose HPs are 1ドル$ and 2ドル$ monsters whose HPs are 2ドル$.