cho.sh

Good Numbers

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.

Hard9CombinatoricsMathSortingImplementationNo attempts yetTime limit2sMemory limit128 MB

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