← 返回题目列表

Codeforces · 652/C

C. 敌人对

中文机器翻译题面 查看原题

给定一个长度为 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)。