题目描述

此题与队列练习1相比有两处改动：1. 加强了数据规模；2. 不保证在队列为空时不会出现出队操作。

给定一个初始为空的队列，只有两种操作：入队和出队。现给出这些操作，请输出最终的队头元素。

操作解释：

• 1 x：将数据 $x$ 加入到队列的尾部；
• 2：从队列中删除队首元素。若此时队空，则此操作无效，并输出 impossible!。

若在所有操作结束后队列为空，也输出 impossible!。

输入格式

第一行一个整数 $N$，表示操作个数。
接下来 $N$ 行，每行一个操作。入队操作为 1 x，出队操作为 2。
所有入队元素均为正整数。

输出格式

若在出队操作时遇到队列为空，则每次输出一行 impossible!；
若所有操作结束后队列为空，也输出一行 impossible!；
否则输出最终队头元素。

样例

5
1 2
2
2
1 3
2

impossible!
impossible!

数据范围

• $1 \le N \le 10^6$
• $1 \le x \le 10^9$