题目描述

以下关于括号序列和括号匹配的定义跟其他题没什么区别，知道的可以跳过。

---

括号序列是一个只包含 $\texttt{(}$ 和 $\texttt{)}$ 的字符串。

定义一个括号序列是合法的，当且仅当它为下列三种之一：

1. 空串是合法的。
2. 如果字符串 $S$ 是合法的，则 $(S)$ 也是合法的。
3. 如果字符串 $S$ 和 $T$ 是合法的，则 $ST$ 也是合法的。

一个合法括号序列中，一个括号是另一个括号所匹配的括号，当且仅当两个括号之间是一个合法的括号序列，且两个括号方向相反。可以证明，一个括号所匹配的括号是唯一的。

---

定义一个括号的匹配发生变更当且仅当它所匹配的括号变更。

你有一个括号序列 $S$。初始 $S$ 为空，下标从 $1$ 开始。

你要进行 $n$ 次操作，操作之间不独立。

每次操作给你两个数 $l,r(0\le l\le r\le |S|)$，表示同时往 $S$ 的 $l\sim l+1$ 之间插入左括号、往 $S$ 的 $r\sim r+1$ 之间插入右括号（$l$ 或 $r$ 为 $0$ 表示在开头插入，为 $|S|$ 表示在末尾插入，$l=r$ 时左括号插在右括号前面）。

可以证明，每次操作完后这个括号序列都是合法的。每次操作完后你需要求这次操作导致匹配发生变更的括号数（不包括新增加的两个括号）。

输入格式

第一行一个数，表示 $n$。

接下来 $n$ 行，每行两个数 $l_i,r_i$，表示一次操作。

输出格式

$n$ 行，每行一个整数。第 $i$ 行表示第 $i$ 次操作导致匹配变更的括号数。

5
0 0
0 0
0 2
2 5
1 2

0
0
0
6
2

提示

样例解释

以下标红的表示新增的括号，蓝色表示当次操作导致匹配发生变更的括号。

• 第一次操作后括号序列变为 $\texttt{\red{()}}$。
• 第二次操作后括号序列变为 $\texttt{\red{()}()}$。
• 第三次操作后括号序列变为 $\texttt{\red(()\red)()}$。
• 第四次操作后括号序列变为 $\texttt{\blue{((\red())(\red))}}$。
• 第五次操作后括号序列变为 $\texttt{(\red(\blue(\red)()\blue)())}$。

数据范围与约定

本题采用捆绑测试。

$$\def\arraystretch{1.2} \begin{array}{|c|c|c|} \hline \begin{array}{c} \tt{subtask}\\\hline 1\\\hline 2\\\hline 3\\\hline \end{array} & \begin{array}{c} n\\\hline \le 10\\\hline \le 10^{3}\\\hline \le 2\times10^{5}\\ \end{array} & \begin{array}{c} \tt{pts}\\\hline 20\\\hline 30\\\hline 50\\\hline \end{array} \\\hline \end{array}$$

对于所有数据，$0\le n \le 2\times10^{5}$，$\forall i \in [1,n],0\le l_i,r_i\le 2\times i-2$。