在茂密的森林里,森林动物运动会正在如火如荼地进行中。各种各样的小动物们排起了长长的队伍,准备参加比赛。

不过因为动物们的体型和身高有所区别,排成的队伍高低错乱,极不美观。

设第 i 个动物的身高为 h_{i} ,我们定义一个序列的杂乱程度为:满足 i 且 h_{i}>h_{j} 的 (i, j) 数量。

动物们的教练每次会选出两个动物,交换他们的位置,请你帮忙计算出每次交换后,序列的杂乱程度。为方便动物们的教练统计,在未进行任何交换操作时,你也应该输出该序列的杂乱程度。

第一行包含一个整数 n ,表示动物的数量。

第二行包含 n 个整数 h_{1}, h_{2}, ..., h_{n} ,表示每个动物的身高。

第三行一个整数 m 表示 m 次交换操作

接下来每行包含两个整数 a 和 b ,表示教练要交换第 a 个动物和第 b 个动物的位置。

输出共 m+1 行,第一行表示初始时候队列的杂乱程度。

第 i+1 行一个正整数表示交换操作 i 结束后序列的杂乱程度。

样例解释:

未进行任何操作时,初始序列为[130, 150, 140],存在满足 h_{i}>h_{j} 的 (i, j) 对,因此杂乱程度为1 。

第一次交换后,序列变为[130, 140, 150],不存在满足 h_{i}>h_{j} 的 (i, j) 对,因此杂乱程度为0 。

第二次交换后,序列变为[150, 140, 130],存在满足 h_{i}>h_{j} 的对有:(1, 3)、(2, 3) 和(1, 2) 因此杂乱程度为3。

【数据范围与提示】

对于40% 的数据,满足 1 ≤n ≤200 , 1 ≤m ≤200

对于40% 的数据,满足 1 ≤n ≤8000 , 1 ≤m ≤2000 。

对于100% 的数据,满足 1 ≤n ≤20000 , 1 ≤m ≤2000 , h_{i} ≤10^{9} , a_{i} ≠b_{i} , 1 ≤a_{i} , b_{i} ≤n