题目描述

工匠老周接到了一份刷漆的活：一条长廊里有 $n$ 个格子排成一行，从左到右编号 $1 \sim n$，最开始所有格子都是白色。

老周会依次进行 $m$ 次刷漆。第 $i$ 次刷漆给出一个区间 $[l_i, r_i]$，他会把这个区间里仍然是白色的格子都刷成颜色 $i$；已经被刷过色的格子保持原来的颜色不变。颜色编号就是操作的编号。

所有操作结束后，请你求出长廊上所有格子颜色编号的总和。仍然是白色的格子按颜色 $0$ 计算。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$），描述一次刷漆。

输出格式

一行一个整数，表示所有格子颜色编号之和。

3 2
1 2
2 3

4

5 2
2 4
1 5

7

3 2
2 2
1 1

3

【样例 1 解释】

• 第 $1$ 次刷漆 $[1,2]$：格子 $1$、$2$ 由白色变成颜色 $1$，长廊变为 $1,1,\text{白}$；
• 第 $2$ 次刷漆 $[2,3]$：格子 $2$ 已经有色，跳过；只有格子 $3$ 由白色变成颜色 $2$，长廊变为 $1,1,2$。

颜色总和 $= 1 + 1 + 2 = 4$，输出 4。

【样例 2 解释】

• 第 $1$ 次刷漆 $[2,4]$：长廊变为 $\text{白},1,1,1,\text{白}$；
• 第 $2$ 次刷漆 $[1,5]$：格子 $2,3,4$ 已经有色，只有两端的格子 $1$、$5$ 被刷成颜色 $2$。

颜色总和 $= 2 + 1 + 1 + 1 + 2 = 7$，输出 7。

【样例 3 解释】

第 $1$ 次刷格子 $2$（颜色 $1$），第 $2$ 次刷格子 $1$（颜色 $2$）；格子 $3$ 从头到尾都没有被覆盖过，按白色（颜色 $0$）计算，总和 $= 2 + 1 + 0 = 3$。

【数据范围】

对于所有测试数据，保证：

• $1 \le n \le 2\times 10^5$；
• $0 \le m \le 2\times 10^5$；
• $1 \le l_i \le r_i \le n$。

• 特殊性质 A：所有操作的区间完全相同（$l_i, r_i$ 都不随 $i$ 变化）。此时只有第 $1$ 次操作能真正刷到颜色，后面 $m-1$ 次全是白跑 —— 把"格子已经有色就跳过"写错的程序会在这些点上给出大得多的答案。
• 特殊性质 B：任意两次操作的区间互不相交（可以相邻）。此时每个格子最多只被一次操作覆盖，颜色的"第一次"与"最后一次"重合，专门用来区分"顺序覆盖"的错解。
• 特殊性质 C：每次操作只刷一个格子（$l_i = r_i$）。
• 特殊性质 D：所有区间都从第 $1$ 个格子开始（$l_i = 1$）。