题目描述

给定一个长度为 $N$ 的整数序列

以及 $Q$ 个询问。第 $i$ 个询问由两个整数 $x_i,y_i$ 描述。

对于一次询问，先将序列中所有值等于 $x_i$ 或 $y_i$ 的位置染色。设染色位置为

我们希望通过交换相邻两个数，使得下式尽可能小：

每交换一次相邻两个数，需要花费 $1$ 元。

对于每个询问，请输出为了使上述双重求和达到最小值所需的最小花费。

输入格式

第一行包含两个正整数 $N,Q$，分别表示序列长度和询问数。

第二行包含 $N$ 个正整数 $a_1,a_2,\ldots,a_N$。

接下来 $Q$ 行，每行包含两个整数 $x_i,y_i$，表示一次询问。

输出格式

输出 $Q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

数据范围

• $2\le N\le 10^6$；
• $1\le Q\le 10^6$；
• $1\le a_i,x_i,y_i\le N$；
• 保证 $x_i$ 和 $y_i$ 都在原序列中出现；
• 保证 $x_i\ne y_i$；
• 保证原序列中至少有两种不同的值。

子任务

一个子任务的分数只有在该子任务及其依赖子任务全部通过时才能获得。

样例 1

输入

5 4
1 2 3 1 4
1 2
1 3
1 4
2 4

输出

1
1
2
2

样例 2

输入

10 6
5 2 1 3 1 3 3 2 1 2
1 2
2 3
3 1
1 5
5 2
3 5

输出

8
4
1
6
11
4