# Problem A

Almost Sorted

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 |