問題文

全ての要素が $0$ の数列 $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$ に書き換える

$Q$ 種類の操作のうちいくつかを行い，$a$ と $b$ のハミング距離， つまり $a_i \\neq b_i$ なる $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