Mr. A's Magic Balls#10363
Sign in

Mr. A's Magic Balls

1.5 seconds
512 megabytes
Very hard

Mr. A discovered a sequence of magical balls in his closet. Each ball is a unique color, conveniently numbered from to . Importantly, is an even number.

Mr. A also has an empty array , where he plans to record the colors of these balls.

He will perform \frac{n}{2} operations, each involving the following steps: Mr. A selects a pair of adjacent balls from the sequence, removes them, and appends their colors to the beginning of array . The order of the colors in will match their order in the original sequence. After removing a pair, the sequence is rejoined, forming a new sequence.

For instance, if the sequence of ball colors is \{1,5,3,2,6,4\}, Mr. A could first add the pair to the start of , then , and finally . This results in the array Q = [1,5,3,4,2,6].

Mr. A wants to know the lexicographically smallest array possible after performing all operations. Lexicographical order is determined by comparing arrays element by element from the start: the first differing element decides which array is smaller. For example, [10, 3, 1] < [10, 4, 5], [1, 1, 1] < [1, 2, 3], and [1, 2, 3] < [10, 10, 10].

Your task is to help Mr. A find the first elements of the smallest possible array .

Input

The first line contains two integers and (1 \le k \le n \le 10^6). It is guaranteed that is even.

The second line contains distinct integers a_1, a_2, \dots, a_n (1 \le a_i \le n), representing the colors of the balls in the sequence.

Output

Output integers q_1, q_2, \dots, q_k—the first elements of the smallest possible array .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  1. ( points): n \le 10^5, k = 1;

  2. ( points): n \le 10^5, k = 2;

  3. ( points): n \le 14;

  4. ( points): n \le 10^3;

  5. ( points): n \le 10^5, k \le 20;

  6. ( points): n \le 10^5;

  7. ( points): without additional constraints.