Sample

A 道路（road）

TIME:2S
Memory:512M

题目描述

费客王国有 $n$ 座城市，费客霞是费客王国的国王，他为自己的国家建立了如下的道路系统：他为每座城市指定了一个等级 $a_i (1 \le i \le n)$（保证城市的等级两两不同），对于任意两座城市 $i ,j (i \neq j)$，都会修建一条从等级高的城市连向等级低的城市的单向道路。

费客霞为这个道路系统感到洋洋得意，但他的子民很快就怨声载道起来：他们发现一旦自己离开了一座城市，就再也不可能回去了！

迫于压力，费客霞又出台了 $k$ 次修正案，每次修正案包含两个整数 $l_i,r_i(l_i \le r_i)$，表示令所有等级介于 $[l_i,r_i]$ 的城市之间的道路反向。（也就是 $\forall u \neq v,a_u,a_v \in [l_i,r_i]$，改变 $u,v$ 之间道路的方向）

考虑到之前子民的诉求，费客霞决定用道路系统中三元环的数量来判断这个道路系统的优劣。请你 帮他计算一下，在 $k$ 次修正案后，道路系统中的三元环数量有多少。

有序三元组 $(a,b,c)$ 被称为三元环，当且仅当同时存在边 $a\to b,b\to c,c\to a$。注意，在本题中，$(a,b,c)(b,c,a)(c,a,b)$ 只会被计算一次。

输入格式

• 从 road.in 读入数据。
• 第一行包含两个正整数 $n,k$，表示城市数量和修正案数量；
• 第二行包含 $n$ 个整数 $a_{1...n}$，表示城市的等级；
• 接下来 $k$ 行，每行两个整数 $l_i,r_i$，描述一个修正案。

  输出格式

• 向 road.out 输出答案。
• 输出仅一行一个整数，表示最终三元环的个数。

样例输入1

4 3
1 2 4 3
2 4
1 2
1 4

样例输出1

2

数据规模与约定

对于$100%$的的数据，$3 \le n \le 2 \times 10^5,0 \le k \le 2 \times 10^5 ,1 \le a_i \le 10^9,1 \le L_i < R_i \le 10^9 $，保证$a_i$互不相同。 不保证$l_i,r_i$与$a_j$相同。

1|10|0|$a_i \le n$ 2|10|10|$a_i \le n$ 3~4|$10^3$|$10^3$|$a_i \le n$ 5~6|$10^5$|$10^5$|无 7~12|$2 \times 10^5$|$2 \times10^5$|保证$a_ia_{i+1}$ 13~20|$2 \times 10^5$|$2 \times10^5$|无