Problem C
Almost Sorted

In a modified version of cycle sort, an array is sorted by swapping pairs of elements such that each swap puts at least one element in its correct final position. Specifically, the algorithm sorts the array in increasing order by performing zero or more sorting iterations on each index, starting from index $i=0$, where a sorting iteration consists of swapping the element $x$ in index $i$ with some other element, such that after the swap, $x$ is sorted. (An element is called sorted if completely sorting the array would not change the position of that element.) This places a new array element in index $i$. These sorting iterations on index $i$ continue until the element in index $i$ is sorted, at which point $i$ is incremented, and the whole process repeats. Eventually, when $i$ has progressed through all valid array indices, the entire array will be sorted, and the algorithm terminates.

In this sorting algorithm, some elements get sorted sooner than others. Given an array, and an element $Q$, it is your task to determine the state of the array when element $Q$ is first sorted.

Input

Input begins with a line containing a single integer $n$, the length of the array $(1\leq n\leq 200\, 000)$. The second line contains the initial state of the array — $n$ distinct space-separated integers, each less than $2^{31}$ in absolute value, beginning with the element in index $i=0$. The last line contains a single integer $Q$, the query. It is guaranteed that $Q$ is one of the elements of the array.

Output

Output a single line containing $n$ space-separated values, the state of the array when $Q$ is first sorted.

Sample Input 1	Sample Output 1
12 4 3 5 10 12 6 8 7 11 1 9 2 8	1 2 3 4 5 6 7 8 11 10 9 12