Kotlin Heroes: Episode 11 |
---|
Finished |
There are $$$2$$$ queues of patients at the doors of two doctors. The first doctor sees patients in the usual order of the queue — whoever arrived first will be seen first. The second doctor does the opposite — he sees those who arrived last first. Thus, there is a queue for the first doctor and a stack for the second doctor. A patient can be in both the queue and the stack. Each patient is characterized by the time their visit to the doctor will take (the time is the same for both doctors).
When the appointments begin, the doctors will see patients in the order of the queue and stack, respectively. As soon as a doctor finishes with one patient, he will call the next one.
But there is one problem: if a patient is in both the queue and the stack, and he is called to one doctor first and then to the other, while he has not yet finished with the first one, confusion will arise. It is allowed for a patient to go to the second doctor at the exact moment he finishes with the first doctor.
The current configuration of the queue and stack is called good if the doctors can see all the patients without any confusion arising.
Initially, both the queue and the stack are empty. There are three types of queries:
It is guaranteed that after each query, each patient is no more than once in the queue and no more than once in the stack.
After each query, you need to determine if the current configuration is good.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of requests.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — for each patient, the time their visit to the doctor will take.
Each of the following $$$n$$$ lines contains two integers $$$t$$$ and $$$x$$$ ($$$1 \le t \le 3$$$; $$$1 \le x \le n$$$) — the type of query and the patient's index. It is guaranteed that:
After each query, print "YES", if the current configuration is good, and "NO" otherwise.
310 15 41 12 12 2
YES NO YES
72 5 1 5 5 4 81 12 51 22 33 21 23 1
YES YES YES YES YES NO NO
In the first test, there are the following configurations:
In the second test, the configuration after query $$$4$$$ is as follows:
After request $$$5$$$, the next configuration is:
After request $$$6$$$, the next configuration is:
Patient $$$2$$$ must be at both doctors at the same time.
After request $$$7$$$, the next configuration is:
Patient $$$2$$$ must be at both doctors at the same time.
Name |
---|