题目描述

小Z正在进行编曲，他要编写一篇情绪高昂的进行曲。

他现有 $n$ 个小节，每个小节的音调是一段 $[l_i,r_i]$ 的连续范围。

为了编曲的新鲜感与花样，小Z决定将某两个相邻的小节进行调换，使得能从调换后的每一小节中，选取一个音符，组成的乐曲的音调能严格递增上升。

询问有多少种交换的方法，能实现上述要求，注意即使相邻两个小节的音调范围完全相同，也可以交换。

输入格式

第一行，一个正整数 $n$，表示小节的数量。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，表示每一小节的音调范围

输出格式

一个整数，表示能完成要求的合法交换数量

输入输出样例

3
0 0
2 2
1 1

1

样例 $\tt \#1$说明

只有交换第二小节和第三小节合法，交换后每小节可以依次选取音符 $0,1,2$，是满足要求的严格递增上升序列。

4
0 5
0 5
0 5
0 5

3

样例 $\tt \#2$说明

三个交换位置都合法。对于每个小节，交换后都可以依次选择音符 $0,1,2,3$。

数据范围

$30\%:n\le2000$

另外 $20\%:$ 对于所有的 $1\le i\le n$ 都有 $l_i=r_i$

$100\%:2\le n\le 2\times10^5,0\le l_i\le r_i\le 10^9$