CF1758F.Decent Division

A binary string is a string where every character is $\texttt{0}$ or $\texttt{1}$. Call a binary string decent if it has an equal number of $\texttt{0}$s and $\texttt{1}$s.

Initially, you have an infinite binary string $t$ whose characters are all $\texttt{0}$s. You are given a sequence $a$ of $n$ updates, where $a_i$ indicates that the character at index $a_i$ will be flipped ($\texttt{0} \leftrightarrow \texttt{1}$). You need to keep and modify after each update a set $S$ of disjoint ranges such that:

• for each range $[l,r]$, the substring $t_l \dots t_r$ is a decent binary string, and
• for all indices $i$ such that $t_i = \texttt{1}$, there exists $[l,r]$ in $S$ such that $l \leq i \leq r$.

You only need to output the ranges that are added to or removed from $S$ after each update. You can only add or remove ranges from $S$ at most $\mathbf{10^6}$ times.

More formally, let $S_i$ be the set of ranges after the $i$-th update, where $S_0 = \varnothing$ (the empty set). Define $X_i$ to be the set of ranges removed after update $i$, and $Y_i$ to be the set of ranges added after update $i$. Then for $1 \leq i \leq n$, $S_i = (S_{i - 1} \setminus X_i) \cup Y_i$. The following should hold for all $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$.

二进制字符串是指每个字符均为 $\texttt{0}$ 或 $\texttt{1}$ 的字符串。若一个二进制字符串中 $\texttt{0}$ 和 $\texttt{1}$ 的个数相等，则称其为“优雅的”（decent）。

初始时，你拥有一个无限长的二进制字符串 $t$，其所有字符均为 $\texttt{0}$。你将收到一个包含 $n$ 次更新的序列 $a$，其中每次更新 $a_i$ 表示将下标为 $a_i$ 处的字符翻转（$\texttt{0} \leftrightarrow \texttt{1}$）。你需要在每次更新后维护并调整一个互不相交的区间集合 $S$，使得：

• 对于每个区间 $[l,r] \in S$，子串 $t_l \dots t_r$ 是一个优雅的二进制字符串；
• 对所有满足 $t_i = \texttt{1}$ 的下标 $i$，均存在某个 $[l,r] \in S$，使得 $l \leq i \leq r$。

你只需在每次更新后输出被加入或被移除的那些区间。在整个过程中，对集合 $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$。

The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of updates.

The next $n$ lines each contain a single integer $a_i$ ($1 \leq a_i \leq 2 \cdot 10^5$) — the index of the $i$-th update to the string.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 更新操作的次数。

接下来的 $n$ 行每行包含一个整数 $a_i$（$1 \leq a_i \leq 2 \cdot 10^5$）—— 第 $i$ 次更新操作所对应的字符串下标。

After the $i$-th update, first output a single integer $x_i$ — the number of ranges to be removed from $S$ after update $i$.

In the following $x_i$ lines, output two integers $l$ and $r$ ($1 \leq l \lt r \leq 10^6$), which denotes that the range $[l,r]$ should be removed from $S$. Each of these ranges should be distinct and be part of $S$.

In the next line, output a single integer $y_i$ — the number of ranges to be added to $S$ after update $i$.

In the following $y_i$ lines, output two integers $l$ and $r$ ($1 \leq l \lt r \leq 10^6$), which denotes that the range $[l,r]$ should be added to $S$. Each of these ranges should be distinct and not be part of $S$.

The total number of removals and additions across all updates must not exceed $\mathbf{10^6}$.

After processing the removals and additions for each update, all the ranges in $S$ should be disjoint and cover all ones.

It can be proven that an answer always exists under these constraints.

在第 $i$ 次更新后，首先输出一个整数 $x_i$ —— 表示第 $i$ 次更新后需从集合 $S$ 中移除的区间数量。

接下来的 $x_i$ 行中，每行输出两个整数 $l$ 和 $r$（满足 $1 \leq l \lt r \leq 10^6$），表示应将区间 $[l,r]$ 从 $S$ 中移除。这些被移除的区间必须互不相同，且均属于 $S$。

随后的一行中，输出一个整数 $y_i$ —— 表示第 $i$ 次更新后需加入集合 $S$ 的区间数量。

接下来的 $y_i$ 行中，每行输出两个整数 $l$ 和 $r$（满足 $1 \leq l \lt r \leq 10^6$），表示应将区间 $[l,r]$ 加入 $S$。这些被加入的区间必须互不相同，且均不属于 $S$。

所有更新操作中移除与添加的区间总数不得超过 $\mathbf{10^6}$。

每次更新完成所有移除与添加操作后，集合 $S$ 中的所有区间必须两两不相交，且其并集恰好覆盖所有值为 $1$ 的位置。

可以证明，在上述约束条件下，答案恒存在。

Line breaks are provided in the sample only for the sake of clarity, and you don't need to print them in your output.

After the first update, the set of indices where $a_i = 1$ is ${1}$. The interval $[1, 2]$ is added, so $S_1 = {[1, 2]}$, which has one $\texttt{0}$ and one $\texttt{1}$.

After the second update, the set of indices where $a_i = 1$ is ${1, 6}$. The interval $[5, 6]$ is added, so $S_2 = {[1, 2], [5, 6]}$, each of which has one $\texttt{0}$ and one $\texttt{1}$.

After the third update, the set of indices where $a_i = 1$ is ${1, 5, 6}$. The interval $[5, 6]$ is removed and the intervals $[4, 5]$ and $[6, 7]$ are added, so $S_3 = {[1, 2], [4, 5], [6, 7]}$, each of which has one $\texttt{0}$ and one $\texttt{1}$.

After the fourth update, the set of indices where $a_i = 1$ is ${1, 6}$. The interval $[4, 5]$ is removed, so $S_4 = {[1, 2], [6, 7]}$, each of which has one $\texttt{0}$ and one $\texttt{1}$.

After the fifth update, the set of indices where $a_i = 1$ is ${1}$. The interval $[6, 7]$ is removed, so $S_5 = {[1, 2]}$, which has one $\texttt{0}$ and one $\texttt{1}$.

样例中的换行仅为了清晰起见，您在输出中无需打印这些换行。

第一次更新后，满足 $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}$。