Robotul gospodar

Lensu has a very large garden and wants to water all $N$ plants lined up next to his fountain. To prevent them from withering by the evening, each plant $i \ (i ∈ {1, 2, \dots, N})$ must receive at least $c_i$ drops of water. Lensu does not want to waste time, so he asks the robotics team to help him build a robot that will do all the work for him.

Although they worked a lot on the robot, its algorithm is quite peculiar. From its current position, our robot will water with one drop per second of staying, all plants in the interval bounded by the closest plant to the left with a required amount strictly less than the required amount of the current plant, and the closest plant to the right with a required amount strictly greater than the required amount of the current plant. If there is no plant to the left with the above property, the robot will water up to plant $1$, and if there is no plant to the right with the above property, the robot will water up to plant $N$.

In the morning, Lensu will give the robot $K$ data of the type:
$X_i$ - the robot's stopping location
$T_i$ - how long (in seconds) it will stay there

Task

Lensu, passionate about algorithms, suspects that the robot is not as efficient as he would like it to be and asks for your help to answer the following question:
Knowing that the robot does not know when the plant's capacity is reached, thus continuing to water the plant if it is within its range, what is the maximum number of plants Lensu could save from withering if he redistributes the wasted drops, watering other plants?

Input Data

The first line contains the number $N$, the second line contains the $N$ required amounts for each plant, the third line contains the number $K$, representing the number of data, and the next $K$ lines contain two numbers $X_i$ and $T_i$, as described in the task. The numbers on the same line are separated by a space.

Output Data

The first line will contain a single number, the answer to the question.

Constraints and Clarifications

• While moving from one place to another, the robot does not water any plants.
• $N \leq 300,000$
• $K \leq 150,000$
• $c_i \leq 1,000,000, \ (i ∈ {1, 2, ..., N})$
• $T_i \leq 1,000,000, \ (i ∈ {1, 2, ..., K})$
• $1 \leq X_i \leq N, \ (i ∈ {1, 2, ..., K})$
• For $20$ points, $1 \leq N \leq 200$

Note

Because there is a lot of input data which has to be read, we recommend using the following instructions at the beginning of the code:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example

stdin

10
3 2 5 1 8 0 4 10 5 3              
4
4 3
7 1
5 2
1 3

stdout

4

Explanation

The robot will execute the first command and will water the plants from position $1$ to position $5$, for $3$ seconds (the closest plant to the left with a smaller capacity than the capacity of plant $4$ does not exist, so it will start watering from the first plant, and the closest plant to the right with a larger capacity than the capacity of plant $4$ is plant number $5$, with a capacity of $8$).

The robot will execute the second command and similarly, after the presented algorithm, will water the plants from position $6$ to position $8$, for one second.

The robot will execute the third command and will water the plants from position $4$ to position $8$, for $2$ seconds.

The robot will execute the last command and will water the plants from position $1$ to position $3$, for $3$ seconds.

At the end of the operations, each plant will be watered for:
$6 \ 6 \ 6 \ 5 \ 5 \ 3 \ 3 \ 3 \ 0 \ 0$ seconds.

It is observed that $15$ drops are wasted, which we can redistribute to save a maximum of $4$ plants.