文化课

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

有 $n$ 名考生从左到右排成一列，第 $i$ 名考生的初始分数为 $a_i$。他希望自己的最终分数不少于 $l_i$，同时又不能超过 $r_i$。

你可以选择若干个互不相交的连续区间组织作弊。所有作弊同时进行；对于每个被选择的区间，区间内所有考生的分数都变为该区间内初始分数的最大值。没有参加作弊的考生分数不变。

请最大化最终分数位于各自区间 $[l_i,r_i]$ 内的考生人数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$。

输出格式

输出一个整数，表示最多能满足要求的考生人数。

样例输入

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

样例输出

6

样例说明

选择区间 $[2,3]$。该区间内两人的分数都变为 $4$，此时所有考生的最终分数都位于各自允许区间内。

数据范围

对于所有数据，$1\le n\le 10^5$，$1\le a_i\le n$，$1\le l_i\le r_i\le n$。

本题采用独立测试点计分。