# Code Forces 652C Foe Pairs

C. Foe Pairs

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation p of length n. Also you are given m foe pairs (ai, bi)(1 ≤ ai, bi ≤ n, ai ≠ bi).

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.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3·105) — the length of the permutation p and the number of foe pairs.

The second line contains n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.

Each of the next m lines contains two integers (ai, bi) (1 ≤ ai, bi ≤ n, ai ≠ bi) — the i-th foe pair. Note a foe pair can appear multiple times in the given list.

Output

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.

Examples

input

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

output

`5`

input

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

output

`20`

Note

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

```#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
#define MAX 3*100000
int a[MAX+5];
int tag[MAX+5];
int dp[MAX+5];
int n,m;
int f[MAX+5];
int x,y;
int main()
{
scanf("%d%d",&n,&m);
memset(tag,0,sizeof(tag));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
tag[a[i]]=i;
f[i]=n;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
int l=min(tag[x],tag[y]);
int r=max(tag[x],tag[y]);
f[l]=min(f[l],r-1);
}

for(int i=n-1;i>=1;i--)
{
f[i]=min(f[i],f[i+1]);
}
__int64 num=0;
for(int i=1;i<=n;i++)
{
int right=f[i];
num+=right-i+1;
}
printf("%I64d\n",num);
return 0;

}```

0 条评论

## 相关文章

### HDU 1403 Eight&POJ 1077(康拖，A* ,BFS,双广)

Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Ja...

32070

### PAT 甲级 1104 sum of Number Segments

1104. Sum of Number Segments (20) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16...

29150

17420

### CodeForces 666B World Tour(spfa+枚举)

B. World Tour time limit per test 5 seconds memory limit per test 512 mega...

34740

### String Problem（KMP+最小表示法）- HDU 3374

Give you a string with length N, you can generate N strings by left shifts. For ...

9320

### ZOJ 3537 Cake(凸包判定+区间DP)

Cake Time Limit: 1 Second Memory Limit: 32768 KB You want to hold a par...

38290

82770

21880

### HDU 4605 Magic Ball Game（可持续化线段树，树状数组，离散化）

Magic Ball Game Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/...

36360

521110