#P18029. Increase Decrease

Increase Decrease

Increase Decrease

给定两个长度均为 NN 的整数序列 A,BA,B。请构造一个 1,2,…,N1,2,\ldots,N 的排列 PP,使得对于每个 1≤i≤N1\le i\le N,前缀 (P1,…,Pi)(P_1,\ldots,P_i) 的最长严格递增子序列长度恰好为 AiA_i,最长严格递减子序列长度恰好为 BiB_i。

子序列可以通过删除若干元素得到,不要求连续,但剩余元素的相对顺序保持不变。若不存在满足要求的排列,输出 −1-1。

输入格式

第一行一个整数 NN。第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。第三行 NN 个整数 B1,…,BNB_1,\ldots,B_N。

输出格式

不存在时输出 -1。否则输出 NN 个整数,表示一个满足条件的排列。若有多个答案,输出任意一个。

数据范围

1≤N≤5×1051\le N\le5\times10^5,1≤Ai,Bi≤N1\le A_i,B_i\le N。所有输入均为整数。

样例 1

输入:

3
1 1 2
1 2 2

输出:

2 1 3

样例 2

输入:

4
1 1 2 2
1 2 2 3

输出:

3 2 4 1

样例 3

输入:

4
1 2 2 3
1 2 2 2

输出:

-1