← 返回题目列表

Codeforces · 501/D

D. Misha 和排列求和

中文机器翻译题面 查看原题

让我们将数字 0, 1, ..., (n - 1) 的两个排列 p 和 q 的和定义为排列 $${\it Perm}((\mathit{Ord}(p)+\mathit{Ord}(q))\bmod n!)$$,其中 Perm(x) 是数字 0, 1, ... 的按字典顺序排列的第 x 个排列, (n - 1)(从零开始计数),Ord(p)是字典顺序中p的排列数。

例如,Perm(0) = (0, 1, ..., n - 2, n - 1),Perm(n! - 1) = (n - 1, n - 2, ..., 1, 0)

Misha 有两种排列,p 和 q。你的任务是找到它们的总和。

排列 a = (a0, a1, ..., an - 1) 被称为按字典顺序小于排列 b = (b0, b1, ..., bn - 1),如果对于某些 k 以下条件成立:a0 = b0, a1 = b1, ..., ak - 1 = bk - 1, ak < bk。

输入

第一行包含一个整数 n (1 ≤ n ≤ 200 000)。

第二行包含 n 个从 0 到 n - 1 的不同整数,用空格分隔,形成排列 p。

第三行包含n个从0到n-1的不同整数,用空格分隔,形成排列q。

输出

打印 n 个从 0 到 n - 1 的不同整数,形成给定排列的总和。用空格分隔数字。

示例

输入 #1

2
0 1
0 1

输出 #1

0 1

输入 #2

2
0 1
1 0

输出 #2

1 0

输入 #3

3
1 2 0
2 1 0

输出 #3

1 0 2

注意

按字典顺序从 0 到 1 的数字排列:(0, 1), (1, 0)。

在第一个样本中 Ord(p) = 0 且 Ord(q) = 0,因此答案为 $$Perm((0+0) \bmod 2) = Perm(0) = (0,1)$$。

在第二个样本中 Ord(p) = 0 且 Ord(q) = 1,因此答案为 $${ \it Perm}((0+1){\bmod {2}})={\it Perm}(1)=(1,0)$$。

按字典顺序从 0 到 2 的数字排列:(0, 1, 2)、(0, 2, 1)、(1, 0, 2)、(1, 2, 0)、(2, 0, 1)、(2, 1, 0)。

在第三个样本中 Ord(p) = 3 且 Ord(q) = 5,因此答案为 $$Perm((3+5) \bmod 6) = Perm(2) = (1,0,2)$$。