二进制字符串是每个字符为 $$$\texttt{0}$$$ 或 $$$\texttt{1}$$$ 的字符串。如果一个二进制字符串具有相同数量的 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$,则称该二进制字符串为正常字符串。
最初,您有一个无限二进制字符串 $$$t$$$,其字符均为 $$$\texttt{0}$$$s。您将获得 $$$n$$$ 更新的序列 $$$a$$$,其中 $$$a_i$$$ 表示索引 $$$a_i$$$ 处的字符将被翻转 ($$$\texttt{0} \leftrightarrow \texttt{1}$$$)。您需要在每次更新后保留并修改一组不相交的 $$$S$$$ 范围,以便:
- 对于每个范围 $$$[l,r]$$$,子字符串 $$$t_l \dots t_r$$$ 是一个不错的二进制字符串,并且
- 对于所有索引 $$$i$$$ 使得 $$$t_i = \texttt{1}$$$,在 $$$S$$$ 中存在 $$$[l,r]$$$ 使得 $$$l \leq i \leq r$$$。
您只需要输出每次更新后添加到 $$$S$$$ 或从 $$$S$$$ 中删除的范围。您最多只能在 $$$S$$$ 中添加或删除范围 $$$\mathbf{10^6}$$$ 次。
更正式地说,令 $$$S_i$$$ 为第 $$$i$$$ 次更新后的范围集合,其中 $$$S_0 = \varnothing$$$ (空集)。将 $$$X_i$$$ 定义为更新 $$$i$$$ 后删除的范围集合,将 $$$Y_i$$$ 定义为更新 $$$i$$$ 后添加的范围集合。然后对于 $$$1 \leq i \leq n$$$,$$$S_i = (S_{i - 1} \setminus X_i) \cup Y_i$$$。以下内容应适用于所有 $$$1 \leq i \leq n$$$:
- $$$\forall a,b \in S_i, (a \neq b) \rightarrow (a \cap b = \varnothing)$$$;
- $$$X_i \subseteq S_{i - 1}$$$;
- $$$(S_{i-1} \setminus X_i) \cap Y_i = \varnothing$$$;
- $$$\displaystyle\sum_{i = 1}^n {(|X_i| + |Y_i|)} \leq 10^6$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 更新次数。
接下来的 $$$n$$$ 行每行包含一个整数 $$$a_i$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) — 第 $$$i$$$ 次更新字符串的索引。
输出
在第 $$$i$$$ 次更新之后,首先输出一个整数 $$$x_i$$$ — 更新 $$$i$$$ 后要从 $$$S$$$ 中删除的范围数。
在接下来的 $$$x_i$$$ 行中,输出两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l < r \leq 10^6$$$),这表示应从 $$$S$$$ 中删除 $$$[l,r]$$$ 范围。每个范围都应该是不同的,并且是 $$$S$$$ 的一部分。
在下一行中,输出单个整数 $$$y_i$$$ — 更新 $$$i$$$ 后要添加到 $$$S$$$ 的范围数。
在接下来的$$$y_i$$$行中,输出两个整数$$$l$$$和$$$r$$$ ($$$1 \leq l < r \leq 10^6$$$),这表示$$$[l,r]$$$范围应该添加到$$$S$$$上。每个范围都应该是不同的,并且不属于 $$$S$$$ 的一部分。
所有更新中删除和添加的总数不得超过 $$$\mathbf{10^6}$$$。
处理每次更新的删除和添加后,$$$S$$$ 中的所有范围应该是不相交的并覆盖所有范围。
可以证明在这些约束下答案总是存在的。
示例
输入 #1
5 1 6 5 5 6
输出 #1
0 1 1 2 0 1 5 6 1 5 6 2 6 7 4 5 1 4 5 0 1 6 7 0
注意
示例中提供换行符只是为了清楚起见,您不需要在输出中打印它们。
第一次更新后,$$$a_i = 1$$$ 的索引集为 $$$\{1\}$$$。添加了区间 $$$[1, 2]$$$,因此 $$$S_1 = \{[1, 2]\}$$$,其中有一个 $$$\texttt{0}$$$ 和一个 $$$\texttt{1}$$$。
第二次更新后,$$$a_i = 1$$$ 的索引集为$$$\{1, 6\}$$$。添加了区间$$$[5, 6]$$$,所以$$$S_2 = \{[1, 2], [5, 6]\}$$$,其中每一个都有一个$$$\texttt{0}$$$和一个$$$\texttt{1}$$$。
第三次更新后,$$$a_i = 1$$$ 的索引集为 $$$\{1, 5, 6\}$$$。去掉区间$$$[5, 6]$$$,增加区间$$$[4, 5]$$$和$$$[6, 7]$$$,所以$$$S_3 = \{[1, 2], [4, 5], [6, 7]\}$$$,每个区间有一个$$$\texttt{0}$$$和一个$$$\texttt{1}$$$。
第四次更新后,$$$a_i = 1$$$ 的索引集为$$$\{1, 6\}$$$。去掉了区间$$$[4, 5]$$$,所以$$$S_4 = \{[1, 2], [6, 7]\}$$$,其中每个都有一个$$$\texttt{0}$$$和一个$$$\texttt{1}$$$。
第五次更新后,$$$a_i = 1$$$ 的索引集为$$$\{1\}$$$。区间 $$$[6, 7]$$$ 被删除,因此 $$$S_5 = \{[1, 2]\}$$$,其中有一个 $$$\texttt{0}$$$ 和一个 $$$\texttt{1}$$$。