给出一个1到n的排列a1,a2,...,an，对它进行冒泡排序。 本题中规定冒泡排序一定是按照下面这段代码这样实现的：

for(i=1;i<=n;i++) 
for(j=1;j<n;j++)
if(a[j]>a[j+1])
swap(a[j],a[j+1]);

现在问题来了！

1.求调用K次swap之后的序列，保证冒泡排序至少需要进行K次swap。

2.给出另一个1到n的排列b1,b2,...,bn，保证它是由原序列调用了若干次swap之后得到的，求次数。

3.学挖掘机技术，到底哪加强。

第一行一个正整数n。 第二行n和正整数a1,a2,...,an。 第三行一个正整数K。 第四行n个正整数b1,b2,...,bn。

第一行n和正整数，表示第一问的答案。 第二行一个正整数，表示第二问的答案。 第三行一个字符串，表示第三问的答案。

样例输入

4
4 3 2 1 
3
1 2 3 4

样例输出

3 2 1 4 
6

数据范围

n<=1000000 其他保证满足题目描述中的要求
对于10%的数据，n很小