该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一条长度为 $N$ 的传送带，上面排着 $N$ 个格子。每个格子里只有两种状态之一：0 或 1。用字符串 $s$ 表示当前状态（下标从 $0$ 到 $N-1$）。

你需要处理 $Q$ 次操作。第 $i$ 次操作给出两个整数 $l_i, r_i$（$0 \le l_i \le r_i \le N-1$），你要把区间 $[l_i, r_i]$ 内的每一位都取反：0 变 1，1 变 0。

每次操作完成后，构造新串

（即在 $s$ 前面加一个 1，后面加一个 0）。

定义函数 $g(t)$：

• 若 $t$ 中存在相邻子串 "10"，你可以选择其中任意一个 "10"，把它替换成 "01"（相当于把这两个相邻字符交换）。
• 重复上述操作，直到 $t$ 中不再出现相邻子串 "10" 为止。
• $g(t)$ 的值等于达到这一状态所需的最少替换次数。

你需要在每次区间取反后输出 $g(t)$。

输入格式

输入共 $Q+3$ 行：

1. 第一行一个整数 $N$。
2. 第二行一个长度为 $N$ 的字符串 $s$（只含 0、1）。
3. 第三行一个整数 $Q$。
4. 接下来 $Q$ 行，每行两个整数 $l_i, r_i$。

输出格式

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 次操作后的 $g(t)$。

输入输出样例 #1

输入 #1

5
01011
2
1 3
0 2

输出 #1

7
10

输入输出样例 #2

输入 #2

3
000
2
0 0
0 1

输出 #2

6
5

说明/提示

• $1 \le N \le 200000$
• $1 \le Q \le 200000$
• 字符串 $s$ 仅由 0 与 1 构成
• $0 \le l_i \le r_i \le N-1$

子任务划分

• $Subtask 1（10）：(N,Q \le 2000)$
• $Subtask 2（15）：(N\le 2e5,\ Q\le 2000)$
• $Subtask 3（15）：(N,Q\le 2e5)$，且所有操作 $(l_i=r_i)$
• $Subtask 4（15）：(N,Q\le 2e5)$，且所有操作满足 $(r_i-l_i\le 50)$
• $Subtask 5（15）：(N\le 5e4,\ Q\le 2e5)$
• $Subtask 6（30）：(N,Q\le 2e5)$（无额外限制）