题目描述

你有两个长度为 $n$ 的数组 $a, b$，其中 $a$ 初始全 $0$ ，$b$ 是给定的由 $0$ 和 $1$ 组成的数组。

你还有 $q$ 种操作，每种操作形如一个区间 $[l,r]$，表示将 $a$ 数组的 $[l,r]$ 区间内的值全部赋为 $1$。

请通过执行 $q$ 种操作中的若干种，最小化满足 $a_i \ne b_i$ 的位置个数。

输入格式

第一行输入一个整数，表示 $n$。

接下来一行 $n$ 个整数，表示 $b$ 数组。

接下来一行一个整数，表示 $q$。

接下来 $q$ 行，每行两个整数 $l,r$，表示可以对区间 $[l,r]$ 进行操作。

输出格式

输出一行一个整数，表示操作后满足 $a_i \ne b_i$ 的位置的最小个数。

样例 1

输入

3
1 0 1
1
1 3

输出

1

样例 2

输入

3
1 0 1
2
1 1
3 3

输出

0

样例 3

输入

3
1 0 1
2
1 1
2 3

输出

1

样例 4

输入

5
0 1 0 1 0
1
1 5

输出

2

样例 5

输入

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

输出

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

输出

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

输出

1

说明/提示

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