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$$$.
6 3 1 3 2 3 5 5
7
For the sample test case, the good subarrays are (1,1) , (2,2) , (3,3) , (4,4) , (6,6) , (1,2) , (3,4).
| Name |
|---|


