A ride-hailing dispatch queue is a singly linked list of fare amounts, in the order rides were requested. Partition the queue around a threshold fare p: all rides with fare STRICTLY LESS than p should come first, in their original relative order, followed by all rides with fare GREATER THAN OR EQUAL TO p, also in their original relative order. Print the resulting fares.
Input format
Line 1: an integer n — the number of rides.
Line 2: n space-separated integers — the fares, in request order.
Line 3: an integer p — the threshold fare.
Output format
n space-separated integers: the fares below p (in order) followed by the fares at least p (in order).
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ fare, p ≤ 1000000000