两个医生门口有$$$2$$$的病人排队。第一个医生按照通常的队列顺序为病人看病——先到的人会先被看诊。第二位医生则相反——他先看最后到的人。因此,第一个医生有一个队列,第二个医生有一个堆栈。患者既可以在队列中,也可以在堆栈中。每个患者的特征都是看医生所需的时间(两位医生的时间相同)。
预约开始时,医生将分别按照排队和堆叠的顺序看诊患者。医生一处理完一个病人,就会给下一个病人打电话。
但是有一个问题:如果一个病人同时在队列和堆栈中,他先被叫到一位医生,然后又叫到另一位医生,而他还没有完成第一个医生的工作,就会出现混乱。允许患者在与第一位医生结束后立即去看第二位医生。
如果医生可以看到所有患者而不会产生任何混乱,则队列和堆栈的当前配置称为良好。
最初,队列和堆栈都是空的。查询分为三种类型:
1. 将患者 $$$x$$$ 添加到队列中;
2. 将患者 $$$x$$$ 添加到堆栈中;
3. 队列中的患者 $$$x$$$ 意识到自己放错了位置,并移至堆栈;然而,他移动到堆栈中的位置,就好像他在进入队列时在查询时进入堆栈一样。
保证每次查询后,每个患者在队列中不超过一次,在堆栈中不超过一次。
每次查询后,需要判断当前配置是否良好。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 请求数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 对于每个患者,他们去看医生所需的时间。
以下 $$$n$$$ 行中的每一行都包含两个整数 $$$t$$$ 和 $$$x$$$ ($$$1 \le t \le 3$$$; $$$1 \le x \le n$$$) — 查询类型和患者索引。保证:
- 如果查询的类型为 $$$1$$$,则患者 $$$x$$$ 尚未在队列中;
- 如果查询的类型为 $$$2$$$,则患者 $$$x$$$ 尚未在堆栈中;
- 如果查询的类型为 $$$3$$$,则患者 $$$x$$$ 已在队列中,但尚未在堆栈中。
输出
每次查询后,如果当前配置良好,则打印“YES”,否则打印“NO”。
示例
输入 #1
3 10 15 4 1 1 2 1 2 2
输出 #1
YES NO YES
输入 #2
7 2 5 1 5 5 4 8 1 1 2 5 1 2 2 3 3 2 1 2 3 1
输出 #2
YES YES YES YES YES NO NO
注意
第一次测试时,有以下配置:
1.队列:$$$[1]$$$;堆栈:$$$[]$$$;患者 $$$1$$$ 由第一位医生看诊 $$$10$$$ 分钟,从 $$$0$$$ 分钟开始。
2.队列:$$$[1]$$$;堆栈:$$$[1]$$$;病人$$$1$$$在$$$[0期间由第一位医生看诊; 10)$$$ 以及 $$$[0 期间的第二个; 10)$$$。由于患者 $$$1$$$ 必须同时去看两位医生,所以答案是“否”。
3.队列:$$$[1]$$$;堆栈: $$$[1, 2]$$$;病人$$$1$$$在$$$[0期间由第一位医生看诊; 10)$$$,以及$$$[15期间的第二个; 25)$$$;患者 $$$2$$$ 在 $$$[0, 15)$$$ 期间由第二位医生看诊。现在,患者 $$$1$$$ 可以在看过第一位医生后去找第二位医生。
第二次测试中,查询$$$4$$$后的配置如下:
- 队列: $$$[1, 2]$$$;
- 堆栈: $$$[5, 3]$$$;
- 病人 $$$1$$$: 第一个医生 $$$[0, 2)$$$,第二个医生没有给他看病;
- 病人 $$$2$$$: 第一个医生 $$$[2, 7)$$$,第二个医生没有给他看病;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人$$$5$$$:第一个医生没有给他看病,第二个医生$$$[1, 6)$$$。
请求$$$5$$$后,下一个配置是:
- 队列:$$$[1]$$$;
- 堆栈: $$$[5, 2, 3]$$$;
- 病人 $$$1$$$: 第一个医生 $$$[0, 2)$$$,第二个医生没有给他看病;
- 病人 $$$2$$$: 第一个医生没有给他看病,第二个医生 $$$[1, 6)$$$;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人 $$$5$$$:第一个医生没有给他看病,第二个医生 $$$[6, 11)$$$。
请求$$$6$$$后,下一个配置是:
- 队列: $$$[1, 2]$$$;
- 堆栈: $$$[5, 2, 3]$$$;
- 病人 $$$1$$$: 第一个医生 $$$[0, 2)$$$,第二个医生没有给他看病;
- 病人 $$$2$$$: 第一个医生 $$$[2, 7)$$$, 第二个医生 $$$[1, 6)$$$;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人 $$$5$$$:第一个医生没有给他看病,第二个医生 $$$[6, 11)$$$。
患者 $$$2$$$ 必须同时到两位医生处。
请求$$$7$$$后,下一个配置是:
- 队列:$$$[2]$$$;
- 堆栈: $$$[1, 5, 2, 3]$$$;
- 病人 $$$1$$$: 第一个医生没有给他看病,第二个医生 $$$[11, 13)$$$;
- 病人 $$$2$$$: 第一个医生 $$$[0, 5)$$$, 第二个医生 $$$[1, 6)$$$;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人 $$$5$$$:第一个医生没有给他看病,第二个医生 $$$[6, 11)$$$。
患者 $$$2$$$ 必须同时到两位医生处。