Description

There are $n$ people taking an academic proficiency exam. Since they pretend that they have retired, the afternoon CPS0202 has nothing to do with them.

Currently, person $i$ has a score $a_i$. To pass, they need to get at least $l_i$ points. To avoid being suspected by the teacher, their score cannot exceed $r_i$.

You may organize several cheating sessions. These sessions happen simultaneously, so no one can participate in two or more sessions at the same time. Each cheating session is carried out on a consecutive segment of examinees, and all their scores become the highest score among them.

Find the maximum number of people who can pass and still not be suspected.

Input Format

The first line contains an integer $n$, meaning there are $n$ people.

The second line contains $n$ integers separated by spaces. The $i$-th number $a_i$ represents the initial score of person $i$.

The next $n$ lines each contain two integers. On the $i$-th line are $l_i$ and $r_i$, with meanings as described above.

Output Format

One line with one integer, representing the maximum number of people who can pass and still not be suspected by the teacher.

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

6

Hint

Organizing one cheating session on $[2,3]$ can make everyone satisfy the conditions.

This problem uses bundled testdata.

• Subtask 1 ($5$ points): $n \le 5$.
• Subtask 2 ($5$ points): $n \le 100$.
• Subtask 3 ($10$ points): $n \le 8 \times 10^3$.
• Subtask 4 ($30$ points): $l_i = r_i$.
• Subtask 5 ($20$ points): $a_i \le a_{i+1}$.
• Subtask 6 ($30$ points): no special properties.

For $100\%$ of the data, $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.

Translated by ChatGPT 5