农夫约翰正在与他的 n 头奶牛举办网球锦标赛。每头牛都有一个技能水平 si,并且没有两头牛具有相同的技能水平。每头牛在比赛中与其他每头牛只打一次,并且每头牛都击败每头技能水平低于自己的牛。
然而,Farmer John 认为比赛会让那些输掉大部分或全部比赛的最弱奶牛士气低落,因此他想翻转一些结果。特别是,在 k 个不同的实例中,他将取两个整数 ai、bi (ai < bi),并翻转技能水平在 ai 和 bi 之间的奶牛之间的所有结果。也就是说,对于任何对 x, y $$( x \neq y ; \; s_{x}, s_{y} \in [ a_{i}, b_{i} ] )$$,他将更改最终记分牌上的比赛结果(因此,如果 x 赢得了比赛,记分牌现在将显示 y 赢得了比赛,反之亦然)。 Farmer John 有可能多次改变一场比赛的结果。不能保证 ai 和 bi 等于某头牛的技能水平。
Farmer John 希望确定他使锦标赛结果看起来有多平衡。特别是,他想计算最终排行榜显示奶牛 p 击败奶牛 q、奶牛 q 击败奶牛 r、奶牛 r 击败奶牛 p 的奶牛三元组 (p, q, r) 的数量。帮助他确定这个数字。
请注意,如果两个三元组不包含同一组奶牛(即,如果一个三元组中有一头牛,而另一个三元组中没有),则它们被视为不同。
输入
第一行是两个以空格分隔的整数 n 和 k (3 ≤ n ≤ 105; 0 ≤ k ≤ 105)。下一行是 n 个空格分隔的不同整数 s1, s2, ..., sn (1 ≤ si ≤ 109),表示奶牛的技能水平。接下来的 k 行是两个空格分隔的整数,ai 和 bi (1 ≤ ai < bi ≤ 109),表示 Farmer John 按照他所做的顺序对记分板所做的更改。
输出
单个整数,包含最终排行榜显示奶牛 p 击败奶牛 q、奶牛 q 击败奶牛 r、奶牛 r 击败奶牛 p 的奶牛三元组 (p, q, r) 的数量。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
3 2 1 2 3 1 2 2 3
输出 #1
1
输入 #2
5 3 5 9 4 1 7 1 7 2 8 3 9
输出 #2
3
注意
第一个样本中,牛 3 > 牛 1,牛 3 > 牛 2,牛 2 > 牛 1。但是,牛 1 和 2 以及牛 2 和 3 之间的结果颠倒了,所以现在 FJ 的结果显示,牛 1 > 牛 2,牛 2 > 牛 3,牛 3 > 牛 1,因此牛 1、2、3 形成平衡三元组。