Foe Pairs

给定一个$1$到$n$数字组成的全排列，同时给定$m$对元素$(a_i,b_i)$。 你的任务是统计有多少个不同的区间$(x,y)(1 \le x \le y \le n)$，这些区间不包含任意一个给定的元素对，即不能同时含有元素对$(a_i,b_i)$的两个元素，这两个元素的先后顺序不限定。 输入格式 第一行，两个整数$n,m(1 \le n,m \le 3 \times 10^5)$ 第二行，$n$个不同的整数，表示一个全排列； 接下来$m$行，每行两个元素$(a_i,b_i) (1 \le a_i,b_i \le n, a_i \neq b_i)$ 输出格式 一行一个整数表示符合条件的区间数量 源码 ``` 给定一个$1$到$n$数字组成的全排列，同时给定$m$对元素$(a_i,b_i)$。 你的任务是统计有多少个不同的区间$(x,y)(1 \le x \le y \le n)$，这些区间不包含任意一个给定的元素对，即不能同时含有元素对$(a_i,b_i)$的两个元素，这两个元素的先后顺序不限定。 输入格式 第一行，两个整数$n,m(1 \le n,m \le 3 \times 10^5)$ 第二行，$n$个不同的整数，表示一个全排列； 接下来$m$行，每行两个元素$(a_i,b_i) (1 \le a_i,b_i \le n, a_i \neq b_i)$ 输出格式 一行一个整数表示符合条件的区间数量 ``` @[chen_zhe](/space/show?uid=8457)

You are given a permutation $ p $ of length $ n $ . Also you are given $ m $ foe pairs $ (a_{i},b_{i}) $ ( $ 1<=a_{i},b_{i}<=n,a_{i}≠b_{i} $ ). Your task is to count the number of different intervals $ (x,y) $ ( $ 1<=x<=y<=n $ ) that do not contain any foe pairs. So you shouldn't count intervals $ (x,y) $ that contain at least one foe pair in it (the positions and order of the values from the foe pair are not important). Consider some example: $ p=[1,3,2,4] $ and foe pairs are $ {(3,2),(4,2)} $ . The interval $ (1,3) $ is incorrect because it contains a foe pair $ (3,2) $ . The interval $ (1,4) $ is also incorrect because it contains two foe pairs $ (3,2) $ and $ (4,2) $ . But the interval $ (1,2) $ is correct because it doesn't contain any foe pair.

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=3·10^{5} $ ) — the length of the permutation $ p $ and the number of foe pairs. The second line contains $ n $ distinct integers $ p_{i} $ ( $ 1<=p_{i}<=n $ ) — the elements of the permutation $ p $ . Each of the next $ m $ lines contains two integers $ (a_{i},b_{i}) $ ( $ 1<=a_{i},b_{i}<=n,a_{i}≠b_{i} $ ) — the $ i $ -th foe pair. Note a foe pair can appear multiple times in the given list.

Print the only integer $ c $ — the number of different intervals $ (x,y) $ that does not contain any foe pairs. Note that the answer can be too large, so you should use $ 64 $ -bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

4 2
1 3 2 4
3 2
2 4

5

9 5
9 7 2 3 1 4 6 5 8
1 6
4 5
2 7
7 2
2 7

20

In the first example the intervals from the answer are $ (1,1) $ , $ (1,2) $ , $ (2,2) $ , $ (3,3) $ and $ (4,4) $ .