odd doctor 已更新

Boring Class

Time Limit
3s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(2/2)
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 L1,L2,...,Ln and R1,R2,...,Rn.
Your task is to find a longest subsequence v1,v2,...vm satisfies
v11,vmn,vi<vi+1 .(for i from 1 to m - 1)
LviLvi+1,RviRvi+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.
1n50000
Both of the following two lines contain n integers describe the two sequences.
1Li,Ri109

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
Source:

2015 Multi-University Training Contest 3


Submit