题目描述

那个夏天，大家在小镇的树荫下约定：一定要找到最适合的秘密基地。

小镇中有 $n$ 个地点，由 $n-1$ 条小路连接，任意两个地点之间都存在唯一一条简单路径。因此，这些地点和小路构成了一棵无根树，地点编号为 $1$ 到 $n$。

每天，大家会按照一个顺序依次来到小镇中的所有地点。这个顺序用一个长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$ 表示，其中 $a_i$ 表示第 $i$ 个被访问的地点。

如果选择地点 $r$ 作为秘密基地，就可以把整棵树以 $r$ 为根。此时，对于两个不同地点 $x,y$，如果 $x$ 位于从 $r$ 到 $y$ 的简单路径上，则称 $x$ 是 $y$ 的祖先。

大家认为，如果某个地点先被访问，而它的某个祖先后被访问，就会产生一次“暴露风险”。形式化地，对于一个秘密基地 $r$，定义危险度 $f_r(a)$ 为满足以下条件的二元组 $(i,j)$ 的数量：$1\le i<j\le n$，且在以 $r$ 为根时，$a_j$ 是 $a_i$ 的祖先。

也就是说，$f_r(a)$ 表示在当前访问顺序下，有多少对地点满足：后出现的地点是先出现地点的祖先。

可是，时间不断流逝，大家的计划也会发生变化。接下来有 $q$ 次操作，每次操作给定一个整数 $x$，表示交换访问顺序中相邻的两个地点 $a_x$ 和 $a_{x+1}$。

在所有操作前，以及每次操作后，你都需要重新选择一个最合适的秘密基地，使危险度尽可能小，并输出这个最小危险度。

输入格式

第一行包含两个整数 $n,q$ ($1\le n,q\le 2\times 10^5$)，分别表示地点数量和操作次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$)，表示初始访问顺序。保证 $a_1,a_2,\ldots,a_n$ 是一个排列。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$ ($1\le u_i,v_i\le n$)，表示地点 $u_i$ 和地点 $v_i$ 之间有一条小路。保证给出的 $n-1$ 条小路构成一棵树。

接下来 $q$ 行，每行包含一个整数 $x_i$ ($1\le x_i<n$)，表示一次操作，需要交换 $a_{x_i}$ 和 $a_{x_i+1}$。

输出格式

输出 $q+1$ 行。

第一行输出初始访问顺序对应的最小危险度。

之后第 $i$ 行输出第 $i-1$ 次操作后的最小危险度。

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

3
3
4
4