给定一个长度为 n 的排列 p。另外,您还获得 m 个敌人对 (ai, bi) (1 ≤ ai, bi ≤ n, ai ≠ bi)。
你的任务是计算不包含任何敌人对的不同区间 (x, y) (1 ≤ x ≤ y ≤ n) 的数量。因此,您不应计算其中至少包含一对敌人的间隔 (x, y)(敌人对中的值的位置和顺序并不重要)。
考虑一些例子:p = [1, 3, 2, 4],敌人对是 {(3, 2), (4, 2)}。区间 (1, 3) 不正确,因为它包含一对敌人 (3, 2)。区间 (1, 4) 也是不正确的,因为它包含两个敌人对 (3, 2) 和 (4, 2)。但区间 (1, 2) 是正确的,因为它不包含任何敌人对。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 3·105) — 排列 p 的长度和敌人对的数量。
第二行包含 n 个不同的整数 pi (1 ≤ pi ≤ n) — 排列 p 的元素。
接下来的 m 行中的每一行都包含两个整数 (ai, bi) (1 ≤ ai, bi ≤ n, ai ≠ bi) — 第 i 个敌人对。请注意,一对敌人可以在给定列表中出现多次。
输出
打印唯一的整数 c — 不包含任何敌人对的不同区间 (x, y) 的数量。
请注意,答案可能太大,因此您应该使用 64 位整数类型来存储它。在 C++ 中,您可以使用 long long 整型,在 Java 中,您可以使用 long 整型。
示例
输入 #1
4 2 1 3 2 4 3 2 2 4
输出 #1
5
输入 #2
9 5 9 7 2 3 1 4 6 5 8 1 6 4 5 2 7 7 2 2 7
输出 #2
20
注意
在第一个示例中,答案的间隔为 (1, 1)、(1, 2)、(2, 2)、(3, 3) 和 (4, 4)。