A chef receives all his orders for the day as a list of unique order ids. He creates a new list by repeatedly removing the smallest eligible order from the current list and appending it to the new list. Return the order in which the chef creates the new list.

An order is eligible in the current list if:

• For an order at index 0, it is eligible if it's orderId is greater than its right neighbor.
• For an order at index n - 1 in a list of size n, it is eligible if it's orderId is greater than its left neighbor.
• For an order at any middle index, it is eligible if it's orderId is greater than both its immediate left and right neighbors.
• When there is only one order left in the list, it is automatically eligible.

Method Signatures

Build Preparation Order

List<Integer> getPreparationOrder(List<Integer> orderIds)

• Returns the order in which the chef appends order ids to the new list.
• At each step, consider eligibility in the current list after all previous removals.
• If multiple orders are eligible at the same time, remove the smallest eligible order id.
• orderIds contains unique values.

Constraints

• 1 ≤ orderIds.size() ≤ 100000
• -10^9 ≤ orderIds[i] ≤ 10^9
• All order ids are unique.

Notes

• Eligibility must always be checked on the current remaining list.
• After removing one order, neighboring relationships may change.
• There is always at least one eligible order in a non-empty list.

Examples

Example 1

getPreparationOrder(orderIds = [5, 1, 4, 2, 3])
Returns [3, 4, 2, 5, 1]

• Initially, the eligible orders are 5, 4, and 3. The smallest is 3.
• After removing 3, the smallest eligible order becomes 4.
• Then the chef removes 2, then 5, and finally 1.

Example 2

getPreparationOrder(orderIds = [1, 3, 2, 5, 4])
Returns [3, 5, 4, 2, 1]

• At the start, 3 and 5 are eligible, so the chef removes 3 first.
• After that, 5 is eligible and is removed next.
• The remaining removals happen in the order 4, 2, 1.

Example 3

getPreparationOrder(orderIds = [7])
Returns [7]

• When there is only one order in the list, it is automatically eligible.

Example 4

getPreparationOrder(orderIds = [9, 2, 8, 1, 7])
Returns [7, 8, 9, 2, 1]

• Initially, the eligible orders are 9, 8, and 7. The smallest is 7.
• After each removal, eligibility is recalculated on the updated list.