A33381.书架

时间限制:1000ms
空间限制:512mb

小X的书架上总是堆满了书。

但是这些书摆放的乱的要命。

一开始，小X的书架上，$n$本书从左到右依次摆放，第$i$本书的编号是$a_i$，保证所有的$a_i$构成了一个$1$~$n$的排列。

现在，小X决定整理这些书。

整理这些书的策略分为$n-1$步，每一步有两个参数$x,y$。

表示的是：将第$x$本书所在的那一列，和第$y$本书所在的那一列，穿插合并。保证每次$x$与$y$不在同一列。

穿插合并的规则是：依次在两列书中从上到下选择一本插s入新的列中，如果某一列书没有了，就把剩下的书按顺序插入。

例如：

例如：$$[1,2,3,4,5,6],[7,8,9]=>[1,7,2,8,3,9,4,5,6]$$

现在，给定小X$n-1$步穿插操作的流程，且保证已经将所有书合成了一列。现在，请你输出这$n$本书从上到下的编号。

第一行输入一个正整数$n$，表示书的个数。

接下来一行$n$个正整数，表示$a_1,...,a_n$，保证这是一个$1$~$n$的排列。

接下来$n-1$行，每行两个正整数$x,y$，表示合并了第$x$本书当前所在的堆以及第$y$本书当前所在的堆。

输出仅一个数字，表示最终的排列$b_1$~$b_n$的每个数字，$b_1*1+b_2*2+b_3*3+...+b_n*n$的结果。

【样例一解释】

最终序列是$[1,3,4,5,2]$,$ans=1*1+3*2+4*3+5*4+2*5=49$。

数据分布

对于30%的测试数据，满足$n\leq 1000$，且$a_i=i$ （附加样例1）
对于70%的测试数据，$n\leq 10^5$,满足数据随机生成（附加样例2）
对于100%的测试数据，$n\leq 10^6$.