育华灯控

题目描述

育华教室有 $n$ 盏电灯。 初始状态下，所有电灯全部处于关闭状态（记为 $a_i=0$）。

我们有一份理想目标状态数组 $b$，$b_i\in{0,1}$，代表第 $i$ 盏灯希望达到的状态，$1$ 代表打开，$0$ 代表关闭。

现在手里一共有 $q$ 种可选操作，每种操作对应一个区间 $([(l,r)])$：执行该操作，会把编号 $l\sim r$ 的所有电灯强制打开（置为1）。 每个操作可以选择执行或者不执行；操作可以选任意多个，顺序不影响最终结果。

执行若干操作之后，统计有多少盏灯实际状态与目标状态不一致。请求出这个不一致数量的最小值。

输入格式

第一行一个整数 $n$，代表灯的数量。 第二行 $n$ 个整数，为目标数组 $b_1,b_2,\dots,b_n$。 第三行一个整数 $q$，代表可选操作的数量。 接下来 $q$ 行，每行两个整数 $(l,r)$，代表一次可选的区间置1操作。

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

样例输入 #2

3
1 0 1
2
1 1
3 3

样例输出 #2

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

样例解释

样例1： 可选操作只有把 $([1,3])$ 全部置1。执行后灯状态为 $([1,1,1])$。 目标 $(b=([1,0,1]))$，第2盏灯不一致，总代价为1。

样例2： 选择操作 $([1,1])$、$([3,3])$。灯光变为 $([1,0,1])$，与目标完全匹配，不一致数量为0。

数据范围

• $1\le n,q \le 2\times 10^5$
• $1\le l_i \le r_i \le n$
• 所有给出的 $[l_i,r_i]$ 互不相同。