Insert into a loop: hints, no solution

A looping playlist is stored as a circular linked list whose values are sorted ascending around the loop, so reading once round from any node you see the values never decrease except once, where the largest drops back to the smallest. You hold a reference to one arbitrary node, so the array you receive lists the values in order starting from that node and going once round.

Insert a new value so the loop is still sorted. Try the gaps in order: first the gap after the given node, then the gap after the next node, and so on, ending with the gap between the last node and the given node. Insert into the first gap that leaves the loop sorted, meaning at most one drop when counting the wrap-around. Return the loop as values starting again from the same given node. An empty loop becomes a loop of just the new value.

Examples

Input

loop = [3, 4, 1, 2], value = 5

Output

[3, 4, 5, 1, 2]

Note

Between 4 and 1 the loop already drops, and 5 is at least the largest, so it goes there.

Input

loop = [1, 3, 5], value = 4

Output

[1, 3, 4, 5]

Note

3 and 5 are the neighbours of 4, so 4 goes between them.

Constraints

• 0 <= loop.length <= 700
• 0 <= loop[i], value <= 1000
• Going round once, the values never decrease except at most once

Hint 1: a nudge

Picture the loop laid out as a circle. Where could a new value fit without creating a second place where the values go down?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing