Description

As everyone knows, student Xiaocong is good at calculations, especially at calculating binomial coefficients, but this problem has little to do with binomial coefficients.

After learning how to compute binomial coefficients, Xiaocong started studying data structures. After fifteen minutes of hard study, Xiaocong initially mastered three data structures: queue, stack, and heap. Xiaocong found that these three data structures all support two operations:

1. Insert a number into the data structure.
2. Remove a number from the data structure according to its rules.

To test his understanding of these three data structures, Xiaocong designed a similar black-box model. This model also supports two operations: input a number into the black box, or output a number from the black box. Now Xiaocong has performed several operations on this black box and provided the number inserted and the number output each time. You are asked whether this black box could possibly be a queue, a stack, a max-heap, or a min-heap.

Although Xiaocong knows these four data structures very well, he still decided to tell you how they differ:

• If the black box is a queue: the black box is initially empty. On input, the number is placed into the black box. On output, the number that was inserted earliest among the current elements in the black box is output and removed.
• If the black box is a stack: the black box is initially empty. On input, the number is placed into the black box. On output, the number that was inserted latest among the current elements in the black box is output and removed.
• If the black box is a max-heap: the black box is initially empty. On input, the number is placed into the black box. On output, the largest value among the current elements in the black box is output and removed. In particular, if there are multiple largest values, only one of them is removed.
• If the black box is a min-heap: the black box is initially empty. On input, the number is placed into the black box. On output, the smallest value among the current elements in the black box is output and removed. In particular, if there are multiple smallest values, only one of them is removed.

Input Format

The first line contains an integer $N$, which represents the number of operations.

The next $N$ lines each contain two integers $\mathrm{opt}, v$. If $\mathrm{opt}=1$, it means that in this operation Xiaocong inserted the number $v$ into the black box. If $\mathrm{opt}=2$, it means that in this operation Xiaocong removed the number $v$ from the black box.

It is guaranteed that $0\leq N\leq 10^5$, $-2^{31}\leq v<2^{31}$, and $\mathrm{opt}\in\{1,2\}$.

Note that the input data is only guaranteed to be completely correct in format and within the ranges, and no other conditions are guaranteed.

Output Format

There are four lines in total. Each line is either Yes or No, indicating whether the black box could possibly be a queue, a stack, a max-heap, or a min-heap, respectively, in this order.

6
1 1
1 2
1 3
2 1
2 2
2 3

Yes
No
No
Yes

Hint

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5