Tohka's favorite food is kinako bread, but she likes to eat bread in general too. For dinner, Shido has bought Tohka N loaves of bread to eat, arranged in a line. Of the N loaves of bread, there are M distinct types of bread numbered from 1 to M. Tohka is very touched that Shido would buy her so much bread, but she is on a diet. Of the i^th type of bread, Tohka doesn't want to eat more than R_i loaves. However, the bread is so tasty that she would like to eat at least L_i loaves of it. Tohka has decided that she will eat all the bread in a consecutive section of the line, and no more. How many ways can she choose a consecutive section of the line to eat?

Input:
The first line of input will have N and M.
The second line of input will have the types of bread in the line, in order, separated from each other by single spaces. It is guaranteed that each type for bread from 1 to M appears at least once.
The next M lines will contain L_i and R_i, for every i from 1 to M.

Output:
The output should consist of one integer on a single line, the number of ways to pick a consecutive section of the line.

Constraints:
1 ≤ M ≤ N ≤ 10⁵
1 ≤ L_i ≤ R_i ≤ N