Pianissimo

Composers use dynamics in sheet music to indicate how loud or soft the notes shall be played. Consider an $8$-scale dynamic system, from softest to loudest: ppp (pianississimo), pp (pianissimo), p (piano), mp (mezzopiano), mf (mezzoforte), f (forte), ff (fortissimo), and fff (fortississimo).

When a musician performs, the absolute loudness of a note matters little. The audience only hears the relative difference. Suppose absolute power is a number, where larger numbers mean larger absolute power. A musician plays all her notes with power up to $100$. When she goes from power $40$ to $70$, some audience may hear her go from p to f, while others may hear her go from pp to mf.

The musician's interpretation must be consistent across the whole piece. Between two notes of different dynamics, the note with the louder dynamic must have a strictly larger absolute power. Between two notes of the same dynamic, their power can vary, usually slightly, but there is no strict requirement.

You just heard a musician perform a piece with $n$ notes. You know the piece well and remember every dynamic the composer wrote. Count the unordered pairs of notes that violate the written dynamics. Such a pair is not necessarily consecutive and can be far apart in the sheet music.

The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 2 \cdot 10^5$), the number of notes and the number of dynamic changes.

The next $n$ lines each contain an integer between $1$ and $10^9$, the absolute power of a note played by the musician. Larger numbers mean larger absolute power.

The next $m$ lines each contain a 1-based index $i$ and a dynamic $d$, meaning that starting from note $i$, the dynamic changes to $d$. Each dynamic is one of the 8 dynamics: ppp, pp, p, mp, mf, f, ff, fff. The indices are distinct and given in increasing order. The first dynamic always starts at note $1$.

Output a single integer, the number of unordered pairs of notes that violate the dynamics.