配点 : $1000$ 点

問題文

全ての要素が $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$

出力

ハミング距離の最小値を出力してください。

3
1 0 1
1
1 3

1

操作を行うと $a = \{1, 1, 1\}$ になり，ハミング距離は $1$ となります。

3
1 0 1
2
1 1
3 3

0

両方の操作を行うと $a = \{1, 0, 1\}$ になり，ハミング距離は $0$ となります。

3
1 0 1
2
1 1
2 3

1

5
0 1 0 1 0
1
1 5

2

何も操作を行わないのが最適な時もあります。

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

3

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

5

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

1