Background

Luogu’s testdata is for community exchange only and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

Spring has come, and the $n$ fields on Xixi-Aifu Island need to be fertilized. The $n$ fields are numbered $1, 2, \cdots, n$, arranged in a line in increasing order of their indices.

To fertilize the fields, Dundun prepared $m$ fertilizing trucks. However, due to different soil softness and different truck weights, not every truck can fertilize every field. Specifically, the $i$-th truck can only exactly drive from field $l_i$ to field $r_i$, and fertilize all fields whose indices are between $l_i$ and $r_i$ (including $l_i$ and $r_i$). Here, $1 \le l_i < r_i \le n$.

Dundun wants to make a fertilization plan. First, he will choose an ordered pair $(L, R)$ ($1 \le L < R \le n$), and decide to fertilize only the fields with indices between $L$ and $R$ (including $L$ and $R$). Then, he will choose some (or all) of the $m$ trucks to fertilize the fields. He wants to ensure that: every field with index in $[L, R]$ is fertilized at least once by some truck, and no field outside this range is fertilized.

Now he wants to know how many different ordered pairs $(L, R)$ he can choose as the fertilization range such that he can select some (or all) trucks to achieve his goal.

Input Format

Read input from standard input.

The first line contains two positive integers $n, m$, representing the number of fields and the number of trucks. It is guaranteed that $2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$.

The next $m$ lines describe the trucks. The $i$-th line contains two positive integers $l_i, r_i$, representing that the $i$-th truck fertilizes from field $l_i$ to field $r_i$. It is guaranteed that $1 \le l_i < r_i \le n$.

Output Format

Output to standard output.

Output one positive integer, the number of different ordered pairs $(L, R)$ that Dundun can choose as the fertilization range such that he can select some (or all) trucks to achieve his goal.

4 3
1 2
3 4
2 3

6

Hint

Explanation for Sample 1

In this sample, Dundun can choose $6$ different ordered pairs $(L, R)$.

The first: choose $(L, R) = (1, 2)$, and select only the $1$-st truck.

The second: choose $(L, R) = (3, 4)$, and select only the $2$-nd truck.

The third: choose $(L, R) = (2, 3)$, and select only the $3$-rd truck.

The fourth: choose $(L, R) = (1, 4)$, and select the $1$-st and the $2$-nd trucks.

The fifth: choose $(L, R) = (1, 3)$, and select the $1$-st and the $3$-rd trucks.

The sixth: choose $(L, R) = (2, 4)$, and select the $2$-nd and the $3$-rd trucks.

Sample 2

See 2.in and 2.ans in the problem directory.

This sample satisfies $n, m \le 18$.

Sample 3

See 3.in and 3.ans in the problem directory.

This sample satisfies $n, m \le 50$.

Sample 4

See 4.in and 4.ans in the problem directory.

This sample satisfies $n, m \le 400$.

Sample 5

See 5.in and 5.ans in the problem directory.

This sample satisfies $n, m \le 3000$.

Sample 6

See 6.in and 6.ans in the problem directory.

This sample satisfies special property A.

Sample 7

See 7.in and 7.ans in the problem directory.

This sample satisfies $n, m \le 200000$.

Subtasks

Special property A: It is guaranteed that for any two trucks, their fertilization ranges do not contain each other. That is, for any $1 \le i < j \le m$, either $l_i < l_j, r_i < r_j$ or $l_i > l_j, r_i > r_j$.

Translated by ChatGPT 5