Good Numbers

Time limit2sMemory limit128 MB

Summary

Given a set S of forbidden integers, rank positive integers by how many good intervals (ranges containing only non-S values) contain each one, then print the first n.

Level: Hard9 of 10
Topics: Combinatorics, Math, Sorting, Implementation
Solved: No attempts yet

Problem

You are given a set S of positive integers. For positive integers A and B with A < B, the interval [A, B] is called a good interval if every integer in [A, B] is not in S.

For a positive integer x, count the good intervals that contain x. If this count for x is smaller than the count for a positive integer y, then x is considered better than y. If the two counts are equal, or if both counts are infinite, the smaller number is considered better.

Sort all positive integers so that better numbers come first according to set S, and output the first n numbers in that order.

Input

The first line contains L, the size of the set S. The second line contains the L integers in S, separated by spaces. The third line contains n, the number of values to output.

Output

Print the first n numbers in the sorted order, separated by spaces.

Constraints

1 ≤ L ≤ 50
The set S contains no duplicate integers.
Every integer in S is at least 1 and at most 1,000,000,000.
1 ≤ n ≤ 100

Examples5

Example 1
Input
```
1
3
6
```
Expected output
```
3 1 2 4 5 6
```
Example 2
Input
```
3
5 11 18
9
```
Expected output
```
5 11 18 1 4 6 10 2 3
```
Example 3
Input
```
3
7 13 18
9
```
Expected output
```
7 13 18 14 17 8 12 1 6
```

Example 4

Input

5
1000 1004 4000 4003 5000
19

Expected output

1000 1004 4000 4003 5000 4001 4002 1001 1003 1002 4004 4999 1 999 4005 4998 2 998 4006

Example 5

Input

1
1000000000
8

Expected output

1000000000 1 999999999 2 999999998 3 999999997 4