n slots holding boxes numbered 1 to n - 1, and one slot is empty. The shelf is described by an array shelf of length n: shelf[i] is the number of the box in slot i, and 0 marks the empty slot. Every number from 0 to n - 1 appears exactly once.
In one move you take any box and put it into the empty slot (the slot it came from becomes empty).
The shelf is in order when the box numbers increase from left to right and the empty slot is either the very first or the very last one. For example, with n = 4 only [0, 1, 2, 3] and [1, 2, 3, 0] count.
Return the minimum number of moves needed to put the shelf in order.shelf=[2, 0, 1, 3] → 2
Move box 1 into the gap: [2, 1, 0, 3]. Then box 2: [0, 1, 2, 3]. Two moves are enough, and one is not.
shelf=[1, 2, 3, 0] → 0
The boxes are already in increasing order with the gap at the end, so no moves are needed.
shelf=[3, 1, 2, 0] → 1
One move is enough: box 3 goes into the empty last slot, giving [0, 1, 2, 3] with the gap now at the front.
shelf is a permutation of the numbers from 0 to len(shelf) - 1shelf=[2, 0, 1, 3]
2
Run checks the first 3 tests in your browser. Submit checks all 164 tests on the server, hidden ones included.