Description

$n$ 个人正在会考。由于他们假装自己退役了，所以下午的 CPS0202 跟他们没啥关系。

目前第 $i$ 个人有一个得分 $a_i$，想要及格需要拿到 $l_i$ 分。而为了不被老师怀疑，他的分数不能超过 $r_i$。

你可以组织若干场作弊。这些作弊是同时进行的，所以不能有人同时参加两场或以上的作弊。每场作弊在连续的一段考生中进行，他们的分数都变为他们中分数最高的人的分数。

求最多能使多少人及格且不被怀疑。

Input Format

第一行一个整数 $n$，表示有 $n$ 个人。

第二行 $n$ 个用空格隔开的整数，第 $i$ 个数 $a_i$ 代表第 $i$ 个人的初始得分。

接下来 $n$ 行每行两个整数，第 $i$ 行的数为 $l_i$ 和 $r_i$，意义见题目描述。

Output Format

一行一个整数，代表最多能使多少人及格且不被老师怀疑。

6
1 1 4 5 1 4
1 1
4 5
1 4
1 5
1 1
4 4

6

Hint

在 $[2,3]$ 组织一场作弊，可以使所有人满足条件。

本题采用捆绑测试。

• Subtask 1（$5$ 分）：$n\le5$；
• Subtask 2（$5$ 分）：$n\le100$；
• Subtask 3（$10$ 分）：$n\le8\times10^3$；
• Subtask 4（$30$ 分）：$l_i=r_i$；
• Subtask 5（$20$ 分）：$a_i\le a_{i+1}$；
• Subtask 6（$30$ 分）：无特殊性质。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le a_i\le n$，$1\le l_i\le r_i\le n$。

• Idea: FZzzz
• Solution: FZzzz
• Code: FZzzz
• Data: FZzzz