P7503 “HMOI R1” Cultural Courses.

A group of people are taking CPS0202. Since cheating can reduce the number of provincial team slots by one, they plan to cheat to harm others, and then get second place in the province in the Gaokao. However, since they are very weak, they cannot get second place in the province in the Gaokao, so they need you to guide them on how to cheat. FZ cannot make this up anymore, and sincerely asks PD to write a Honkai Impact 3 style background for him.

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.

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.

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

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