Counting Subarrays
Description
You're given an integer $N$ which is the length of an array and also given $M$ Subarrays. You need to find the number of good non-empty subarrays in the array. A subarray is considered $Good$ if it doesn't fully contain any of the $M$ given subarrays. In other words, for every "Good" subarray $[a,b]$, there should not exist an $i$ such that $a \leq l_i$ and $r_i \leq b$.
The first line contains a single integer $N ( 1 \le N \le 10^9)$, the length of the array. The second line contains a single integer $M ( 1 \le M \le 3 \times 10^5)$ , the number of ranges. Each of the next $M$ lines contains two integers $l_i$ and $r_i$ separated by a single space, indicating the range of the $i_th$ subarray. $(1 \le l_i \le r_i \le N)$
Output a single integer, the total number of $Good$ $Subarrays$.
Input
The first line contains a single integer $N ( 1 \le N \le 10^9)$, the length of the array. The second line contains a single integer $M ( 1 \le M \le 3 \times 10^5)$ , the number of ranges. Each of the next $M$ lines contains two integers $l_i$ and $r_i$ separated by a single space, indicating the range of the $i_th$ subarray. $(1 \le l_i \le r_i \le N)$
Output
Output a single integer, the total number of $Good$ $Subarrays$.
6 3
1 3
2 3
5 5
7
Note
For the sample test case, the good subarrays are (1,1) , (2,2) , (3,3) , (4,4) , (6,6) , (1,2) , (3,4).