Partition An Array

easy

1. You are given an array(arr) of integers and a pivot.
2. You have to re-arrange the given array in such a way that all elements smaller or equal to pivot lie on the left side of pivot and all elements greater than pivot lie on its right side.
3. You have to achieve this in linear time.

Note -&gt; For more information, watch question video.

Input Format

An Integer n arr1 arr2.. n integers An integer pivot

Output Format

Check the sample output and question video.

Constraints

1 &lt;= N &lt;= 100000
-10^9 &lt;= arr[i] &lt;= 10^9
-10^9 &lt;= pivot &lt;= 10^9

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

Swapping -2 and 7
Swapping 1 and 7
Swapping 3 and 4
-2 1 3 7 4

Merge Sort

Quick Sort