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: add patient (x) to the queue; add patient (x) to the stack; patient (x), who was in the queue, realizes he is in the wrong place and moves to the stack; however, he moves to the position in the stack as if he had entered the stack at the moment of the query when he entered the queue. 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