Boring Class

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Mr. Zstu and Mr. Hdu are taking a boring class , Mr. Zstu comes up with a problem to kill time, Mr. Hdu thinks it’s too easy, he solved it very quickly, what about you guys?
Here is the problem:
Give you two sequences ${L_1,L_2,...,L_n}$ and ${R_1,R_2,...,R_n}$.
Your task is to find a longest subsequence ${v_1,v_2,...v_m}$ satisfies
$v_1 \geq 1$,$v_m \leq n$,$v_i < v_{i+1}$ .(for i from 1 to m - 1)
$L_{v_i} \geq L_{v_{i+1}}$,$R_{v_i} \leq R_{v_{i+1}}$(for i from 1 to m - 1)
If there are many longest subsequence satisfy the condition, output the sequence which has the smallest lexicographic order.


Input

There are several test cases, each test case begins with an integer n.
$1 \leq n \leq 50000$
Both of the following two lines contain n integers describe the two sequences.
$1 \leq L_i,R_i \leq 10^9$

Output

For each test case ,output the an integer m indicates the length of the longest subsequence as described.
Output m integers in the next line.

Sample Input

5 5 4 3 2 1 6 7 8 9 10 2 1 2 3 4

Sample Output

5 1 2 3 4 5 1 1

Hint

wange2014

Source

2015 Multi-University Training Contest 3

提交代码