问题描述

给定一个由 $N$ 个元素组成的序列 $a = \\{a_1, ..., a_N\\}$，其中所有元素都为零，以及一个由 $0$ 和 $1$ 组成的序列 $b = \\{b_1, ..., b_N\\}$。两个序列的长度都为 $N$。

你可以执行 $Q$ 种操作。第 $i$ 种操作如下：

• 将 $a_{l_i}, a_{l_i + 1}, ..., a_{r_i}$ 中的每个元素替换为 $1$。

通过执行一些操作，使得 $a$ 与 $b$ 的汉明距离最小化，即 $a_i \\neq b_i$ 的元素对数最少。

约束条件

• $1 \\leq N \\leq 200,000$
• $b$ 由 $0$ 和 $1$ 组成。
• $1 \\leq Q \\leq 200,000$
• $1 \\leq l_i \\leq r_i \\leq N$
• 如果 $i \\neq j$，则 $l_i \\neq l_j$ 或 $r_i \\neq r_j$。

---

输入

输入从标准输入读取，格式如下：

$N$ $b_1$ $b_2$ $...$ $b_N$ $Q$ $l_1$ $r_1$ $l_2$ $r_2$ $:$ $l_Q$ $r_Q$

输出

打印出最小可能的汉明距离。

---

示例输入1

3
1 0 1
1
1 3

示例输出1

1

如果选择执行这个操作，$a$ 将变为 $\\{1, 1, 1\\}$，汉明距离为 $1$。

---

示例输入2

3
1 0 1
2
1 1
3 3

示例输出2

0

如果同时执行这两个操作，$a$ 将变为 $\\{1, 0, 1\\}$，汉明距离为 $0$。

---

示例输入3

3
1 0 1
2
1 1
2 3

示例输出3

1

---

示例输入4

5
0 1 0 1 0
1
1 5

示例输出4

2

不执行任何操作可能是最优选择。

---

示例输入5

9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7

示例输出5

3

---

示例输入6

15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13

示例输出6

5

---

示例输入7

10
0 0 0 1 0 0 1 1 1 0
7
1 4
2 5
1 3
6 7
9 9
1 5
7 9

示例输出7

1